I had this problem when I had a faulty message rule. It said if the email was FROM 'me' move it to a specified folder. I did this to test emails would go to a test folder. WRONG, most incoming emails actually went to the deleted folder. I removed the message rule and the fault cleared.