ここしばらく英語系ML用のアカウントを検索フォルダベースで運用してみた*1のですが、メール数が3000通程度で既に遅くて辛い状態になってしまいました*2。サーバの性能などにも拠るので一概には言えませんが、サーバでの検索に関してサーバソフトで何らかの対処をしないと常用するのは難しそうです。
*1 IMAP4の検索コマンドで検索しています
*2 ローカルでマクロを使って検索すれば多少は速いです