Are they actually being moved to the Deleted Items folder?
My guess is that you have set your view to show unread item only.
Use the View menu to set your view back to the Messages view or reset the
Messages view.
See http://www.msoutlook.info/question/322
