The iPhone app reMail is email search the way it should be:
iPhone mail search is fine. reMail iPhone mail search is actually good, if it works for you. Two things: there's no Exchange support (sorry suits!), and there's only support for one account at a time. But within that one IMAP or POP account, reMail archives all your message text as far back as you want, letting you search full text-not just subjects-without a network connection.
But now it's gone from the App Store, because Google just bought the company, and its developer, Gabor Cselle, is now a Gmail product manager (he actually got his start working on Gmail).