Each item that you delete from your inbox or Sent Items folder is moved to the Deleted Items Folder.

In order regain the space these items used up in your mailbox, they must be cleaned out of the Deleted Items folder. This can be done by right clicking on the deleted items folder and clicking Empty Deleted Items or turning on the automatic empty deleted items upon exit in your Options menu.

This feature can be turned on from Tools>Options>Other, The General tab at the top has a check box to turn on "Empty the Deleted Items Folder upon exit".

Each time you exit Outlook you will be asked to agree that you want to remove all the items in your Deleted Items folder.