If you're really worried about the worst-case behavior of regular expressions be sure to select an engine designed specifically to not choke on pathological inputs, such as Russ Cox's RE2:

http://code.google.com/p/re2/

The rather interesting analysis is here:

http://swtch.com/~rsc/regexp/regexp1.html

Not that it's a free lunch, since you're gaining a constant amount of overhead in exchange for a sane growth pattern.

EDIT: Of course the article would mention RE2. That's what I get for reading the comments before TFA...