Mutt has a built-in feature for search the body of emails in the current mailbox (see ESC-b) but it's also possible to make this extremely fast by plugging-in external tools. Here's a quick description of my mairix setup.

After installing the package,
apt-get install mairixcreate a .mairixrc in your home directory containing something like:
base=/home/username/Mail
maildir=inbox:archives*:sent*
mbox=debian*:jokes
mfolder=search
database=/home/username/Mail/.mairix_database
(This assumes that you store your mail in ~/Mail and that you want the search results in a new ~/Mail/search maildir folder.)

Then you need to run mairix once to index all of your emails:
mairix
which you will of course want to run regularly. I created this cronjob in /etc/cron.d/mairix-username:
17,37,57 * * * * username /usr/bin/on_ac_power && /usr/bin/mairix(To avoid waking up the hard drive needlessly, I prefer to restrict the indexing runs for when I'm running on AC power. Take that out if you're not running it on a laptop.)

Finally, the last bit of setup is in ~/.muttrc:
macro index \eb 'c=search'<enter><shell-escape>'mairix ' 'Enter Mairix search term'
which makes mairix take over the ESC-b shortcut.

If you use GPG, you should also add this to your ~/.muttrc to make sure that mairix can see all of your messages by saving them as clear text:
set fcc_clear=yes
bind index s decrypt-save
bind pager s decrypt-save