There are a few things that can cause this. You may have already tried some of these so forgive me if I tell you something you already know.
1. Make sure that you've not only deleted messages from your Inbox but also from the Sent Items and any other folders that you have.
2. Above the lists of message is a line that has Show Messages From: and then a box that probably says "last 10 days". Hit the down arrow to the right of that and select something like "last 75 days" or "the beginning". You may have messages in the folders that aren't showing up in the lists. Then you can delete those too. You will have to do this in each folder.
Try those and post back here if you're still having problems.
