By its very nature, this regular expression will match quickly when it *does* match, but consume enormous amounts of time when it doesn't match.  Sorry, but "tough luck" is the only answer here.  O'Reilly publishes a very good book, "Mastering Regular Expressions", by Jeffrey Friedl, that explains why in detail.  Don't have time to write a book here <wink>, but, as a general hint, whenever you have nested repetition ("+" inside a "+" group, etc), unless you know exactly what you're doing you're going to cause *any* "NFA" regexp engine to take exponential time in the cases the regexp doesn't match.

Bring it up on comp.lang.python!  I'm sure someone will take the time to show you how to write the regexp in a way that works better.  Or buy the book.  Or don't use regexps for this problem to begin with.