I think when you delete it moves it to the Trash folder, then you have to delete all the messages in the trash.