@grocanar : il se peut aussi, voire surtout, qu'il y ait un blocage par un serveur de lutte anti-spam, genre sorbs. La construction de serveur de mail perso est mions "surveillée" avec des &fixes.

Il esdt donc possible que ton fai ait déclarée la plage d'adresses que tu utilises à un serveur anti-spam, donc black-listées...

regarde aussi si ton fai utilise les enregistrement MX ...

$ host -t MX ton_fai

sinon, tu dois pouvoir contourner en utilisant ton fai comme smart host, et
tes clients restent en smtp.ton_domaine.truc ; ton postfix s'appuiera alors sur le smpt.ton_fai.tru

relay-host=smtp.mon_fai.fr

Ajout: dans main.cf
Cordialement