Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
Go to your Mail preferences->Accounts->Mailbox Behaviors. Are your deleted messages set to go to the Trash folder? If that's already enabled, consider rebuilding the mailboxes by going to the Mailbox menu and selecting the Rebuild option at the bottom of the list. Instructions for reindexing can be found here.
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.