aptitudeでmutt-patchedを入れてみたのだけど、どうやらheader cacheという機能がついているみたい(-patched無しだとどうなるかは知らない)。
これを有効にしてIMAP4でGmailから受信してみたら、二回目以降が激速。というかこれでAlpineとかClaws Mailと同じになった感じです。
set header_cache=yes
これなら常用できるかも。
2009-12-03 追記
まちがえた。
set header_cache=~/.mutt_cache
とかファイル名にしないと、いつの間にかyesという名のキャッシュファイルができている罠。