Ich denke auch, daß es ein Problem mit der Namensauflösung ist. Schau doch mal in die /var/log/mail. Wenn dort so etwas steht wie "unable to get canonical name of client", dann ist es definitiv die Namensauflösung. Dann IP und Rechnernamen in die /etc/hosts eintragen und fertig.