I've never actually used it, so I may be shooting myself in the back here, but at http://perl.plover.com/Regex/ is regex.pm, a teaching module which uses a DFA algorithm which (or course) doesn't backtrack - ever. DFA's are faster than NFA's but we don't get a lot of neat stuff. I avoid using the package because I trust Perl to perform losts of complex optimizations behind my back, using math I don't understand, most of the time. For this reason it has been suggested that Perl's regexes be renamed IRregular expressions, because Perl uses a mish-mash of algorithms to optimize for the common case.

If you use Regex.pm /tell me about it. I'd love to know how it went.