Guess I'll have to ask in the Gentoo forums then. But well... aliasing grep to pcregrep removed this slowness and I can use the regexes I love. :-)