Two cases that could be causing your issue:
1. If you access email via POP, you can tell Outlook to leave a copy of the message on the server. In this case, the message would show up as a saved message on the phone as opposed to new. There is also a setting to delete the message when deleted from Deleted Items. Both settings are in More Settings -> Advanced in Account Configuration.
2. If you use cached Exchange mode in Outlook, there is a delay between when you delete the message and when it's deleted from the server. Outlook first writes changes to the message store on your local hard drive and then to the Exchange server.
Hope this helps.
Brandon