Make sure your Outlook is set to download the messages from the server, Not just pull the header from the server.
This sounds to be the case, Sounds like youve pulled the headers from server, then when you delete the "Message" your just deleting the header, and leaving the message on the server. When you do an update from the email server does it show the message again?