I've used mutt for ages, but a couple of years ago I switched to Karel Zak's mutt-kz branch (https://github.com/karelzak/mutt-kz), which integrates notmuch into mutt. The setup is a little fussy (although well documented), but the results are spectacular. Mutt's search was never horrible but with notmuch its nutty fast, and the tagging feature makes dealing with search and mailing lists very convenient.