I have an Android 4.0 tablet, set up email and when I delete some - put them in the trash, and them empty the trash, they're still there when I look in that folder again.
What kind of email account is it? It sounds like you don't have it set to delete the messages from the server when you delete them from the phone (so the next time it syncs, it downloads them again). Check in the email account "incoming" settings.