Ok, I _think_ I have the stuff more or less covered by now.  Here is
the gist of what I think it does:

you can go back to earlier changes and non-changes with ^.  You'll get
highlighting for the changed or unchanged region as proper.
Replacements and stuff for the _current_ match will still work out
even if you edit in between (by using markers to save the match-data),
but if you edit before _previous_ changes, you'll get into trouble
(the change _history_ does not use markers for efficiency reasons).
All markers (or at least the significant majority) get destroyed
explicitly, so there should be no marker-induced delays apparent.

Editing of _regexp_ replacement strings (I can't with good conscience
make \? do something special in non-regexp replacements) can happen
with \?.

The current version should not be significantly slower than
previously, with possibly one exception: when doing massive
replacements with map-query-replace-regexp, each replacement will get
scanned for possibly occuring \? strings _each_ time.  Since
map-query-replace-regexp is probably not the most frequent function to
use, I doubt this is very relevant, though.

Please check out the patches: I had to make several changes to
search.c which had, as far as I am concerned, several bugs and needed
amendments of the save-data structures, too.

\? is not yet documented.  I _think_ it makes a nice addition.  The
way it works also makes it abundantly clear that one should enter
explicitly backslash-quoted strings as answer to \?, since one is
editing the replacement string.

Here are the patches for src/search.c and lisp/replace.el against
current CVS.  Note that the changes, including API change of
match-data t, that I have done to search.c is strictly bugfix
material: the previous behavior was inconsistent and partly wrong.
Whether or not people want \? in the current form in the code, the
changes in search.c are necessary also to get replace.el work
correctly even in its previous form.

That is not to say that I am convinced the new code is bugfree: I am
convinced it is necessary, and I became exposed to this necessity by
working on replace.el.  So please take a double careful look at the
changes in search.c: they affect _a_ _lot_ possibly, and I am
particularly not certain that the garbage collector and general Lisp
machinery will be fine with saving last_thing_searched (which can be a
buffer) away the way I do.  I am a doctor, not an engine...  I mean,
I am a C programmer, not Lisp, no a Lisp... whatever.  I don't have a
clue about the C aspects of Emacs' Lisp machine.

Even if people don't check this out, I'll check it in eventually.