When you are viewing your inbox or sent items etc. above where the list of message is located there are the words Show Messages From: and then a pull down box. Hit the arrow on the right of that box and select "from beginning". This will probably show messages that are still there but have been there long enough that they weren't showing up.
If they now show up, you can delete them and you should be set.