Most of the time, when I've had trouble with regex performance, it has been because I was trying to use the regex to do more than it needed to do, particularly with nested data. Usually a better approach is to break the input up into discrete, manageable tokens and then apply my 'hairy regex' in a more controlled and targeted manner.

Of course, that doesn't really answer your question. But it may make your question moot ... :)