Sure it is deleted... but it ain't thrown in the trash.
Or if you tell Evo to Empty the trash, it'll get rid of all deleted messages.
At one point I had 15GB of un-removed messages that were deleted.
You could also have Evo "Empty the Trash" when you close it... taking a few moments of time to trash the stuff.
I ain't quite seeing where that is though, for the auto expunge on close. Running Evo 2.4.2.1