В Gmail сообщения хранятся не менее 30 дней после присвоения им ярлыка 'deleted'.