Cada email enviado e recebido passa por um servidor (neste caso, um servidor do Gmail).
O servidor registra e mantém um registro do remetente e do destinatário de cada e-mail, além de outras informações, como registro de data e hora, e a conexão com outros servidores.
Como o Gmail é um servidor de webmail, as mensagens ESTÃO em seus servidores. A interface da web é apenas uma maneira de visualizar os emails.
Então, eles não têm apenas o log, eles têm as mensagens e sabem seu conteúdo.
Em sua política de privacidade, eles dizem:
Our automated systems analyze your content (including emails) to provide you
personally relevant product features, such as customized search results,
tailored advertising, and spam and malware detection.