Postfix - Host or domain not found

Your server is trying to use IPv6 when sending the mail. Since the mail.example.com doesn't have an AAAA-record (which is the same as an A-record, but for IPv6), that isn't working.

If you want Postfix to never use IPv6, you can change that in the config file, as explained in the postconf(5) man page:

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

If you want to change it for this domain only, change your transport map to read

example.com smtp-ipv4:[mail.domain.com]