Replace all occurrences in large search-replace operations

Wrote a test to demonstrate the issue, no fix yet.