This appears to be a either a bug or just an inconsistency in functionality between mail clients.
I just tried an experiment. I have my ME account set up in Outlook as IMAP. I'm pretty sure that the Mac mail app is also IMAP.
When I delete a message, it remains in the inbox but is lined out. Syncing the IMAP folders to the server (Send/Receive) doesn't change the status of the messsage on MM.
Now, back in Outlook, I purge deleted messages then sync again. Now with a MM refresh, the message is gone.
So what is happening, when a message is "deleted" on the iPhone, it really only Flags it for deletion. Then when you Actually delete a message in MM, it also takes with it the other items that have been flagged either from the phone, or your mail client.
I'm sure this will all be straigtened out in future updates.