Maybe you’re trying to erase any lingering virtual sweet nothings of an ancient romance, or maybe you’re trying to wipe all sign of your top secret government job; whatever the case may be, you’d probably expect a deleted e-mail to stay deleted.
That’s just not the case with the current iPhone OS.
A fellow by the name of Matt Janssen was searching for something on his iPhone through OS 3.0’s new homescreen search when he noticed it: some of the results shouldn’t be there. Sure, they were relevant to the search keywords – but these results were emails that were supposed to have been deleted long ago.
So Matt ran another test: he sent himself an email, then deleted it from his iPhone. He cleared his trash, and then ran the search again. Sure enough, there it was. “Perhaps it’s being pulled from the server?”, he thought. So he deleted all trace of it from the server, and ran the search again. It still showed up. The iPhone was apparently caching old emails, with some as old as 4 months still popping up.
Always skeptical, we ran the same test ourselves. The first time around, all worked as one would expect. We deleted the email, cleared the trash, ran the search, and.. nothing. The email was gone. We were about to write it off as some sort of sham or fluke, when we ran the test a second time. On the second run through, everything happened just as Matt said it would; our once dead email had risen from the grave.
While the likelihood of someone nabbing your phone and guessing the subject line is arguable, the fact that such potential is there is bad enough. If you’re doing something you’re not necessarily supposed to be doing, the virtual fingerprint is but a quick search away – and all any potential sleuth needs is a bit of the subject line.
[Via Cult of Mac]

An internal tipster has provided Gizmodo with a tip saying that Apple will probably issue a fix in the iPhone OS 3.1 update.
Source: http://www.gizmodo.com/5339305/uh-oh-iphone-os-30-never-fully-deletes-your-emails-updated
Talk about lack of privacy.
Privacy from your own phones search functionality. OMG how did my iPhone know I made all of those 1+900 calls. LOL
Who can still use an iphone for corporate needs?
People use the iPhone for corporate needs?
Yes, it runs rings around the other phones for productivity.
Really? Fart apps constitute “productivity” now days?
I’d be interested in what you mean by productive. Is it managing your calendar? Editing documents? Browsing the web? Chatting? All of this can be done on other phones (some have had these functions longer than the iphone)
Good lord this is old news and it’s just coming up now.
Hope you didn’t find this out the hard way :)
I checked it on my own phone and it pulls up deleted emails easily.
DOH!
I have this problem on a daily basis, only I don’t even need to perform a search to find the already deleted and emptied from the trash e-mails. I can go to sleep and wake up only to find 34 e-mails that all seem to be the same exact ones that I erased the day before. E-mail on the iPhone is horrific, the only true way to get e-mail is through mobileme. I am experiencing issues with yahoo pushing my e-mails to my phone and gmails new gpush app is a total joke, it notified me of the first three e-mails once I launched it and entered my username and password and since then it hasn’t notified me of the other 20 plus emails I have received. Conclusion: iPhone and e-mail just don’t mesh well unless you are willing to dish out $99 a year for mobileme which works 95% of the time. I have issues with mobileme sending messages on occasion and that is all.
No problem for me. My phone has a security code on and I usually do not let others to use my phone or to know the code.
In fact this feature is handy if you accidentally deleted an important e–mail. Think more about it.
Can’t understand all this buzz… Do you, guys, really leave your phone around for everyone to explore its content? This is not the brightest thing to do with any phone!
And, yes, it is used for corporate work and it is a good one for productivity together with CalenGoo, OmniFocus and a couple of other apps. Other phones might be good too but it is a question of personal preference. iPhone helped me a lot and I am really a busy guy (just had 5 mins to look to mobilecrunch between meetings).