Now this is an interesting problem.

One solution that I could think of right off the bat is to add a marker to the beginning and ending of the replacement string before applying it, and then not allowing the search string to operate in the area bounded by an open/close marker. Remove the markers before emitting the output.

If you do follow this approach, watch out for greedy matching. By your definition, you should never have nested "this is changed" markers, so a minimal match on the search string should suffice.