When you delete a message, it is really just moved to the Deleted Items folder. And, it stays there until one of the following things happen:
You Empty the Deleted Items Folder
Your Network Administrator Empties the Deleted Items Folder
The Deleted Items folder in Outlook is a little like the Recycle Bin folder for Windows. Every now and then, you should empty your Deleted Items folder.
Right-click the Deleted Items Folder
Choose Empty “Deleted Items” Folder