Next question: may I guess that you weren't using MULTIBYTE in 7.2?
After still more digging, I'm coming round to the opinion that the
problem is that MULTIBYTE is forced on in 7.3, and this imposes a
factor-of-256 overhead in a bunch of the operations in regcomp.c.
In particular, compiling a case-independent regex is now hugely
more expensive than it used to be.
The parties who wanted to force MULTIBYTE on promised that there
would be no such penalties :-(
regards, tom lane