Probier mal mit "nslookup domain" die Domain des Absenders manuell zu resolven. Könnte es sein, daß dein nameserver nicht richtig konfiguriert ist ?
Hier hat auch jemand auch so ein ähnliches Problem:
http://www.perl.jann.com/sendmail/200009/msg01141.html