mutt has excellent OpenPGP and GPG support. However different clients send GnuPG encrypted/signed data in different ways. Lots of people seem to be using FireGPG these days so that they can use GnuPG within the GMail/Hotmail/Yahoo! web clients.

Here's the procmail rule I used to convert almost all incoming emails to the OpenPGP/MIME format:
:0
* !^Content-Type: multipart/
* !^Content-Type: application/pgp
{
:0 fBw
* ^-----BEGIN PGP MESSAGE-----
* ^-----END PGP MESSAGE-----
| formail \

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.)

Since mutt seems to be all the rage these days at work, I might as well document here a few things about my .muttrc that might be useful to others.

(I recommend that you start off with the Debian or Ubuntu package for mutt since a large chunk of necessary customization work has already been done by the Debian maintainers.)