Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> Maybe there's a misunderstanding.  What Noam suggested was just to
>> move the code which adjusts search_regs.start[i] and .end[i] to before
>> the call to replace_range.
>
> Oh, right, that's also an option.  It might suffer from another problem,
> which is that the match-data will be broken while the
> before-change-functions are run, so if there's a save-match-data there
> we're back to square one.

Solution: adjust in between the before and after change functions.
Patch below.  I think there shouldn't be performance problems, although
it does add yet another flag to replace_range (by the way, I noticed
that the MARKERS flags is never 0, so it's redundant).  I tested with
the attached bug-23917-match-data-buffer-modhook.el.