I don't have much experience using regexes on Unicode strings (and that only in the distant past), so this is a stab in the dark, but might some of the slowdown be due to the regex processing changes made to accommodate Unicode? Perl version 5.8 was more or less in the midst of those changes IIRC.

If you're not, in fact, dealing with Unicode text, maybe check out the discussion in Character set modifiers (and other places) WRT the /a and /aa "ASCII-safe" modifiers.