Here's my current mental model of how Elasticsearch would handle the additional
!deletedfiltering predicate...
This is not how ES works. There's more info on query/filter execution here: In which order are my Elasticsearch queries/filters executed? | Elastic Blog
The best way to evaluate this is perhaps to build it and try it out. Note that we use similar kind of filtering already internally when you have nested types defined. Nested documents are proper documents in Lucene (but miss a certain internal field), and automatically filtered out of searches based on the absence of that internal field. You could do something similar, only add this "deleted" field to tombstone docs, and then filter them out as documented here.