у меня тоже mutt + vim. поиск — очень хороший, когда вынужденно приходится пользоваться другими клиентами (web, android, macosx) — то поиск, это то, чего больше всего не хватает. 15K писем в Maildir открывает (сейчас проверил) за полсекунды. метки/теги — это поле X-Label в заголовке. Можно по нему искать и фильтровать.