I wrote Regexp::Approx - Use fuzzy regular expressions (and forgot to submit it to CPAN) to solve the re-entrant regex problem for my specific problem. I forked during INIT, kept some file handles pointing to and from the child and then would send all the re-entrancy-requiring work to the child.

You could pre-fork a number of children and then create more as needed. Alternatively, you could create a backtracking module for us and allow us to stop abusing regexes just to get at an already written engine.