Following Our Leader, I’ve just switched to using notmuch with mutt for searching (instead of maildir-utils, previously). I strongly recommend this setup to all mutt users.
As a bonus, accented characters (é, è, …) are now handled correctly while searching, which is quite useful in french.
Good! Now you’ll just have to switch to Emacs as a mail reader :)
+1 for emacs, you can switch to emacs + wanderlust . it has amazing offline imap support and look wise much better then other emacs client.