when you stop and think about it tho, gmail is almost like a hard drive. if you delete something, someone with the right power, machines, and/or skill can get what they want off of it untill it has been written over many times.
Seeing as how servers are made of hard drives, (considering the size of google, it has to be in the millions if not billions) its not all too suprising that your email is not truely deleted for a while. afterall, the odds of multiple people getting emails to that spot on a that drive, and deleteing it in a short time are kinda small.