mutt in your terminal of choice, to a local Maildir structure synced from your IMAP server, plus your search utility of choice.
The obvious tradeoff the relative lack of polish and overhead during initial setup, but if you're willing to put up with that it's a fine choice.