connection to mail exchanger failed

Hallo Zusammen,
ich habe einen 2003 SBS mit Exchange Server.

alles ist Standard eingerichtet:

es gibt einen MX-Record und den ReverseDNS eintrag.

Probleme gibt es grundsätzlich keine.

Ein User beklagt sich über folgende Fehlermeldung:

"connection to mail exchanger failed"

Einen SPF-Eintrag gibt es nicht.

Ich vermute mal es ist ein Problem bei der gegenstelle aber ich wollte mal eure Meinung dazu hören...

Danke