There is an option to "Empty Deleted Items Folder Upon Exiting"
If this option is selected that would explain the problem. To check (and change it) Go to TOOLS --> Options. Under the "Other" Tab - this is the first option. Make sure the check box is blank. This should solve the problem, but remember you will have to empty the deleted items manually if you do this. I would suggest leaving it, and instead of deleting things you're not sure if you're going to want, set up another folder and move the mail there until you are sure.
I hope this solves it for you.
Take care