Grepmail looks for mail messages containing a pattern, and prints the resulting messages. Usage is very similar to grep. It can handle compressed mailbox files, and can search the header or body of emails. It also supports searches constrained by date and size.
Lucas N. suggested grepmail. This utility is most useful with mbox style mail folders. Of course, if one stores email in Maildir format, a simple grep -rl pattern Maildir/ will do the trick. Well, minus the header/body features of grepmail. But then, you might as well use perl if you want to do that (better regexes too).
More information on this package can be found on the Debian web site.
(If there is a package you would like to see featured here, go to the userinfo page and follow the directions there to submit your entry.)