How can I search for emails on an IMAP (or exchange) server?
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.