For Gmail, Google keeps backups of mail boxes and their transaction log. This way they can rewind the mailbox over a period of weeks.

It's basically a continuous backup.