I found the answer… I was just a bit stupid (didn't sleep for a while ^^). When iterating a string in reverse order, it does not matter that the length changes:
for (NSTextCheckingResult *result in [[exp matchesInString:string optinos:NSMatchingReportCompletion range:NSMakeRange(0, [string length])] reverseObjectEnumerator]) {
// …
}