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 mairix

create 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 || true

(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
bind index \ec decrypt-copy
bind pager \ec decrypt-copy