How can I search for emails on an IMAP (or exchange) server? Is there an app that can search emails by subject, sender or body text through the IMAP4 protocol?

Alternatively, is there an app that caches the email headers for all messages and searches them locally?
K9 (IMHO the best Mail client for android) currently lacks this feature. If you want this feature, please vote for it without leaving "I want this too comments"

I don't know of any other alternatives.