make sure the mailbox updates
I had that happen once when open mail it contects to the servers and downloads your messages. When you delete the messages and go into the Trash you have to check the bar at the bottom and it should show you the time the folder was updated. If you lose connection to the web or you close the app too fast it doesn't perform the delete on the server side because your connection is not active.