So yes, I'd say query-replace is very likely to be most complex case
there will be.  And it has several unique features that make it quite
different from other potential uses of lazy highlight:

- The splitting of the TO and FROM strings at "->".
- The value of case-fold-search can change on the fly
- We must clean up the highlight only if the user quits, to avoid
  flickering at the beginning of the perform-replace stage.

Okay, as I write this I realize occur would require some special stuff
if the region is active.  This indeed should be factored out.  But
hopefully you will agree with the 3 points above :-).

>> Right, a preview of the replacement text will also need some extra work.
>> This will probably involve some extension to
>> 'isearch-lazy-highlight-update', making it even more complicated...
>
> Why?  Shouldn't it just highlight the same way the text
> entered into the minibuffer that reads the replacement?

I'm referring to the anzu feature whereby the replacement text is shown
next to each match, like this: