After some messing around, I think I figured it out. Josh, I used your offer to start. I'm not sure if you edited your sentence or simply deleted it, but it left, so I cannot quote it in your answer.
In any case, you need to shift the ranges that you are going to replace after each call to replaceCharactersInRange:withString: otherwise bad things will happen, because the ranges do not match. Here is what I ended up with:
This works great and supports cancellation, as expected, canceling this operation will result in all replacements being canceled immediately.
Anyway, thanks to Josh, as his answer made me point in the right direction.
source share