I'm heavily afraid this is a FAQ, but I couldn't find anything. Short form: My impression is that not fully qualifying the value of relaylhost causes Postfix to only look up AAAA records for it.
Long form: I'm on NetBSD 6.0_BETA/amd64 with the supplied Postfix 2.8.8. Basically I have the default configuration but myorigin=$mydomain and relayhost=smtp (I also have two masquerade options, full postconf -n at the end). Apperantly, Postfix only tries to look up an IPv6 address for "smtp": I get Host or domain name not found. Name service error for name=smtp type=AAAA: Host not found and warning: relayhost configuration problem Fully qualifying the relayhost parameter (e.g. relayhost=smtp.math.uni-bonn.de) solves the problem. Is this a known issue? May it be NetBSD (or NetBSD 6.0) specific? Full postconf -n output (AFTER the change): command_directory = /usr/sbin config_directory = /etc/postfix daemon_directory = /usr/libexec/postfix data_directory = /var/db/postfix debug_peer_level = 2 html_directory = /usr/share/doc/html/postfix inet_protocols = all mail_owner = postfix mailq_path = /usr/bin/mailq manpage_directory = /usr/share/man masquerade_classes = envelope_recipient masquerade_domains = math.uni-bonn.de myorigin = $mydomain newaliases_path = /usr/bin/newaliases queue_directory = /var/spool/postfix readme_directory = /usr/share/examples/postfix relayhost = smtp.math.uni-bonn.de sample_directory = /usr/share/examples/postfix sendmail_path = /usr/sbin/sendmail setgid_group = maildrop unknown_local_recipient_reject_code = 550