I was hoping that this bug would have been fixed in the new 1.1.1 firmware release but it wasn't. So I got creative and found a pretty simple but effective solution. Here's the bug I'm talking about... If you are an Exchange server user, when you delete a message on the iPhone, it doesn't really delete the message on the Exchange server. So, when you fire up your e-mail client on your computer (e.g. Outlook), you end up still seeing all of the mail that you thought you deleted via your iPhone. Those "non-deleted" messages show up as "read" but they are still there. So you have to delete them again in your computer's e-mail client. Here's my fix... In addition to my normal Exchange e-mail account in Outlook on my computer, I created a new IMAP account which hits the same Exchange server. As soon as I did that, it fixed the problem of deleted mail still hanging around. What seems to happen is that when Outlook hits the Exchange server, both the Exchange account and the IMAP account check for mail and update their respective inboxes (obviously). Well, the Exchange account on Outlook doesnt know what to do with the deleted but shown as just read stuff from the iPhone. But the IMAP account does know what to do with it. It goes ahead & purges the deleted stuff from the iPhone and presto!, the Exchange account inbox on Outlook also loses the iPhone-deleted items. I really hope we get real Exchange integration some day (I know, I know, "the iPhone isn't a business-user device"). But in the mean time, this solves what (in my opinion) had to be the most annoying bug out there related to using the iPhone with an Exchange server.