Well, this is a pain in the butt: by default, when you create an IMAP or Exchange account on the iPhone, messages you delete aren’t ever actually purged from the server. The effect of this is that messages you delete on the iPhone don’t disappear from your Outlook/Entourage/Exchange ActiveSync/whatever mailbox, leading to angst if you’re trying to keep a tidy inbox.
The fix is simple, once you know it exists: Tap Settings > Mail, select the IMAP account, tap Advanced, then select the purge interval from the “Deleted Messages” group. (Apple has a cursory document on it here). The problem is that the shortest interval is 1 day– so when you remove a message on the iPhone, it will take 24hr to disappear from your other clients. This is a pretty poor “feature” and I’m disappointed that Apple didn’t take the time to implement proper deleted item purging as they do in Mail.app. Boo hiss.
Update: another annoyance is that the iPhone insists on creating its own Deleted Items folder in the Inbox. That’s just wrong. I suspect this can be fixed by modifying the server path prefix, but that shouldn’t be necessary. The whole point of having a defined account type for Exchange is to avoid this kind of problem (that’s why the iPhone correctly hides other folders, like Calendar and Contacts).