dont know if it applies in your case.
Have you created any message rules? Delete or change them if you did,may solve the problem.
Messages coming from blocked senders in OE will also go to the deleteditemsfolder
You may have inadvertantly placed some of your contacts into the 'blocked senders list'
Tools,Message Rules,Mail Blocked Sender.