Looks like we're not the only ones who are having problems deleting mail on the iPhone. Dynamic Solutions Group, EdH on Mac Forums, and others throughout the world wide webs are having problems.
Turns out that the mail client on the iPhone marks messages for deletion, yet never sends the purge command to actually delete the message. The end result is that when we delete a message on the iPhone, then later log into Outlook, the deleted message remains.
That's why we wrote Expunge (named after the IMAP command). It's a simply command line application that asks you for your mail server, username, and password and periodically purges deleted mail items on your behalf.
I'm sure Apple will release a fix for this bug soon. In the meantime, download the Expunge binary. If you'd like you can also have the C# 2.0 source code.