I believe it is a known fact that repeated repeats, like (...+)*, make for slow matching (if they work at all) with the current re engine.
[I would not be surprised if Perl does some special casing to (in effect at least) rewrite the re to your second version.] This is not going to be improved in 2.7, nor immediately in 3.x. You can try the regex module on pypi, but it may act the same. I suspect there are similar issues like this on the tracker. Best to write the re properly.

[Antoine or Ezio: If you think I am mistaken in closing this, please reopen.]