Some years ago I tried to create an exponential time regex in Perl, and only managed a quadratic time one after a bit of experimenting.

But, as you said, quadratic is often already fatal on realistic data.