In iPhone OS 3.0, the act of deleting an email doesn’t necessarily mean it is immediately gone forever, it’s actually cached for a while.
Matt Janssen created a YouTube video that demonstrates deleted messages can be retrieved via a simple Spotlight search on your iPhone or iPod touch. Janssen claims he has found emails from three to four months ago using this method. Don’t believe it? Try it out for yourself.
You can test the flaw by creating an email message with a memorable subject (just so it’s easier to find), and then delete it. Go to your Trash and remove it from there as well. Check your mail server (IMAP and POP both work) to ensure you have completely erased it. Then, go to Spotlight and search for your memorable subject. Your search results should show the message and in many cases, the entire message itself.
The messages do eventually disappear, but there is just no telling when. There have been reports of simple workarounds, like viewing the deleted message three to four times, but this method would be overly tedious if you want to ensure every single message is completely removed from your device. According to Gizmodo, Apple is aware of the issue and will hopefully be including a fix in the official release of iPhone OS 3.1.
[via Cult of Mac]
So… It’s just the normal operation of Spotlight’s indexing but considered a flaw because you can undelete messages and possibly dig up personal info.
Personally… I don’t see this as a big deal. Something to modify on Apple’s end but I don’t see some kind of huge rush. Why?
1) If you lose your iPhone / iPod touch with 3.0 software and have MobileMe, you can remote wipe it. If you don’t have MobileMe and can’t wipe it… You have more than just recently deleted emails to worry about.
2) If someone has physical access to your iPod touch or iPhone that you wouldn’t want to recover these emails, you need to take care of the source.
Someone prying into your personal information is a bigger problem than just being able to undelete email. 
3) It will eventually update the index file and fully delete the email.
On a plus side. You can undelete emails that you recently completely removed. Kind of like a free backup.
Once again, I agree with you. This isn’t as much of a bug as it is intended behavior with an unexpected result. However, it is confirmed, at least in the beta iPhone OS 3.1, that this doesn’t occur.
Thank you so much for sharing this flaw. You literally saved me!