The iPhone was launched without the capability to search emails. It took until iPhone OS 3.0 for this feature to be introduced. Unfortunately, the search feature is still limited to the headers (i.e. to, from, subject etc). You are not able to search the body of the messages (full-text search). This is a quite severe limitation, in particular for mobile business users.
reMail is an iPhone app that solves this. If reMail sounds familiar, it’s probably because they’re a Y-Combinator start-up and that they’ve been featured on TechCrunch. In the article on TechCrunch, the reMail Beta was criticized due to privacy concerns, as the version reviewed actually stored and processed the messages on reMail’s servers. In recent versions, this is no longer the case (as TechCrunch also pointed out in a follow-up article). This is fortunate, because I’m not sure how comfortable I would have been with all my emails sent to their servers (even if they back then claimed the data was safely stored).
Getting started with reMail is simple. After a configuration wizard where you provide the app with your IMAP settings, reMail connects to your server to download the messages onto the device. You’re strongly advised to have your device connected to WiFi during this process, both because of speed and to avoid expensive cellular bills. If you have multiple accounts that you’d like to add to reMail that’s possible too.
Once you’re done adding accounts and downloading the messages, you’re able to perform full-text search on your mailbox(es). You’re even able to perform more sophisticated (boolean-style) searches, such as ‘subject: foobar’ or ‘meeting -washington’.
Another great feature that reMail adds is the ability to set up a “Smart Inbox” similar to what you’ll find in Apple Mail, where you have all your email accounts displayed in one view. All you need to do is to configure reMail to download all your inboxes. Moreover, you can use reMail to reply to a message using the built-in Mail app. Unfortunately it does not format the message as nicely as the native Mail app.
For those of you who leave the civilization frequently, you’ll be pleased to find that you’re able to use reMail even in offline mode (simply because the messages are stored locally).

The only limitation I found with reMail (other than the formatting of replied messages), was the fact that it cannot run in the background. Yes, I know, this is no fault of the developers of the reMail, it’s a limitation in the iPhone, but it would still be nice.
reMail is priced at $4.99, which I find very reasonable. While I’d rather have seen this feature built into the iPhone, I suppose this is the next best-thing. I wouldn’t be surprised if reMail receives a phone call from Cupertino with an acquisition offer, as full-text search is very important in the business world.
It is also worth mentioning that there is a free version of reMail that is limited to Gmail (I’m not sure if it works with Google Apps too).
Links:

[...] This post was mentioned on Twitter by Email marketing, etc, Email Service Guide. Email Service Guide said: reMail Completes Mail On The iPhone http://bit.ly/2mJtqH @remaildotcom #remail #iphone [...]