Acho que o problema está nos scripts de instalação, postfix.preinst
tem algum código interessante sobre isso e alguns comentários:
Add a 'mydomain' entry in main.cf for upgrade? Postfix version 2.3.3-2 and later require changes in main.cf. Specifically, mydomain must be specified, since hostname(1) is not a fully qualified domain name (FQDN). . Failure to fix this will result in a broken mailer. Decline this option to abort the upgrade, giving you the opportunity to add this configuration yourself. Accept this option to automatically set mydomain based on the FQDN of the machine.*