Wie sieht es mit Mail-Relay Einstellungen aus? Die meisten Mailer sind so konfiguriert das sie prinzipiell nur für Nutzer des lokalen Rechners bzw. der lokalen Domäne relayen/weiterleiten. Was steht den in den Logfiles (/var/log/postfix o.ä.)? Evtl. poste mal die Konfigurationsdatei.

Gruss,
Ronnie