lookahead/lookbehind assertions are rather expensive if the string being matched is long
demerphq might be too shy to toot his own horn, but a couple of weeks he landed an awesome patch to the development version of Perl that teaches the optimiser to look inside those assertions and use the information to improve the matching strategy used. Which equates to some massive speedups in some cases, perhaps the cases to which you were alluding.
Let's just hope that Perl 5.10 sees the light of day soon. There's lots of goodness in there waiting to be unleashed.
• another intruder with the mooring in the heart of the Perl