The regex engine was updated in version 7.4 and now is noticeably faster.
The best solution would probably be to switch to PCRE. Some Vim-specific stuff[1] would have to be special-cased, but Vim could get an order of magnitude speedup (and fix quite a few bugs) by using a modern, optimized, well-tested regex library.
1. Vim abuses regexes like nothing I've ever seen. You can even match line and column numbers with the regex engine: http://vimdoc.sourceforge.net/htmldoc/pattern.html#/\%l