reMail	iPhone 3.0 Mail
Searches From/To
Searches Subjects
Searches Full-text
Autocompletes Names
Search History
Saves attachments on iPhone
Advanced search operations (prefix, not, or, etc.)
Marks up matches
Searches time (recent / old messages)	0.5s / 2s	0.5 s / 10 s
Messages stored on phone	All	50-200
Search scope	All Mail	Current folder only

reMail is powerful full-text email search, not header-only search like iPhone Mail. reMail offers a number of advanced search features such as prefix search and boolean operators.

reMail stores all your email on your phone, not just the most recent messages for each folder: That's why for older messages, reMail is 5x faster in finding emails than iPhone Mail's server search.