Oh, man - I think I just found a fix. It seems as though you have to re-sync the phone after you delete the message/messages.
Now, my phone is setup to sync manually. If yours is setup to sync hourly, daily, or weekly you shouldn't have to do this. You would, however, have to wait for your phone to re-sync at it's set time. Of course, if you don't want to wait you can use the refresh button at anytime when you are in your email box on your phone.
The only issue I'm running into now is when I delete emails on my phone that are from my Gmail account they don't show up in my Gmail trash folder on my PC. I can search within Gmail and find them (I have to since they don't show in my inbox anymore) but I have no idea where they are actually being stored. I don't have this problem with Hotmail though. All Hotmail messages deleted from my phone show in the deleted folder in Hotmail.