Regexps can be implemented in mainly 2 ways: backtracking or not.
If you don't do backtracking, the above problem doesn't occur.
But many/most regexp implementations use a backtracking algorithm
because it's almost indispensable in order to handle backreferences.
Emacs provides backreferences and doesn't bother to provide 2 regexp
implementations (a backtracking one for regexps with backrefs and
a non-backtracking one for all the others), so you get pathological
behaviors for regexps such as the one above. It's too bad, and I hope
we can fix it at some point, but don't hold your breath,
This comes up often enough that maybe it should be explained in one
of the manuals.