They have decided to anonymize their server logs after 18-24 months, which is a step in the right direction, but, of course, more can and should be done.

I think the next step would be when a user chooses to "delete forever" their e-mail it should really be deleted forever and not have any backup copies on Google servers whatsoever. Same for drafts and Google Documents and such.

What do you guys think should also be done to respect user's privacy?

The problem with "delete forever" really erasing any footprint is quite impossible for a security reason: what if someone enters into your account and deletes every important mail? You *need* a complete and real backup...
I'm happy with current privacy policy, anyway.

Zim, if someone enters into your account and deletes every important mail, I doubt Google are going to do a custom restore from their backup just for you.

I think a "delete forever" that works properly would be ideal. Not some kind of "delete after we've made a copy for the government" though.