I'm thinking we should go with LIKE. This is MySQL 4.0.21 on Gentoo Linux on a Pentium III 866.
mysql> SELECT DISTINCT(physmessage_id) FROM dbmail_messageblks WHERE messageblk LIKE '%From:%Aaron%'; 11089 rows in set (31.17 sec) [cpu hovered around 50%] mysql> SELECT DISTINCT(physmessage_id) FROM dbmail_messageblks WHERE messageblk REGEXP '.*From:.*Aaron.*'; 11089 rows in set (10 min 44.80 sec) [cpu was pegged solid at 99.9%] Aaron