I think you can do the same optimisation even in that case, if you augment the spending block with its corresponding revNNN.dat data. You can’t authenticate the revNNN.dat, so still need to track negative entries, and in addition also need to check that the rev data was correct (compare it to the utxo when you find a match), and need to be able handle falling back to in-order processing (in case you’re given bad rev data which says a tx is invalid, you need to recheck when you get the actual utxo data, if it’s different).
(I was thinking of that technique in the context of taking an assumeutxo set and validating the chain both forwards and backwards simultaneously, to avoid the need to maintaining two utxo sets, provided you didn’t care about optimising for the case where the assumeutxo point was actually invalid)