Seu servidor está tentando usar o IPv6 ao enviar o e-mail. Como o mail.example.com
não tem um registro AAAA (que é o mesmo que um registro A, mas para o IPv6), isso não está funcionando.
Se você quiser que o Postfix nunca use IPv6, você pode mudar isso no arquivo de configuração, como explicado na página man postconf (5):
When IPv6 support is enabled via the inet_protocols parameter, Post-
fix will do DNS type AAAA record lookups.
When both IPv4 and IPv6 support are enabled, the Postfix SMTP client
will attempt to connect via IPv6 before attempting to use IPv4.
Examples:
inet_protocols = ipv4
inet_protocols = all (DEFAULT)
inet_protocols = ipv6
inet_protocols = ipv4, ipv6
Se você quiser alterá-lo apenas para este domínio, altere seu mapa de transporte para ler
example.com smtp-ipv4:[mail.domain.com]