This fixes the problem in the only simple way I could think of.
A new configuration option is added "hbase.hregion.increment.supportdeletes" which defaults to true (because it is required for "correctness").
When this option is true, then when the scan against StoreFiles is done, it will also include the MemStore. This should ensure correctness for cases where delete markers are present in the MemStore that need to apply to KVs in the StoreFiles.
I made this a configuration option because it makes increment operations less optimal, so for increment workloads that do not need to support deletes, they can keep the option turned off and avoid the double scan of the MemStore.
A potential optimal and correct solution to this could be to use the old Get delete tracker which would retain delete information across files (for in-order file processing rather than one mega merge). Some work is going into re-integrating those, so if they do make it back in the HBase, we could utilize them here.
This should suffice for now.