Found it...
Just found the GMail privacy policies related to deleted items. The section is quoted below.
Your choices
- You may change your Gmail account settings through the Gmail "settings" section.
- You may organize or delete your messages through your Gmail account or terminate your account through the Google Account section of Gmail settings. Such deletions or terminations will take immediate effect in your account view. Residual copies of deleted messages and accounts may take up to 60 days to be deleted from our active servers and may remain in our offline backup systems.
- You may choose to use additional Gmail features, such as Google Talk. The Google Talk service has its own privacy notice available here.
The question is, what is Google’s backup policy? How long do they retain mail I delete? May be time to stop using GMail.