what's wrong with grep(1)?

OK, I should not be so surprised anymore, but what the hell, man? What's wrong with grep that it's so horribly slow sometimes?

$ ls -lgoh mbox
-rw-r--r--  1   75M Feb 15 17:14 mbox

$ time /opt/grep/bin/egrep '^M|^begin|^end$' mbox | wc -l

real	11m15.924s
user	9m50.645s
sys	1m18.155s

$ time awk '/^M/ || /^begin/ || /^end$/' mbox | wc -l

real	0m2.110s
user	0m2.532s
sys	0m0.176s
(GNU grep 2.6-cvs, 2009 / awk version 20040207)