We are getting this error occassionally (not often) when a user tries to send an email. In the recent case, the CEO gets the same error whether sending from our local office email account (exchange) or from his corporate office email account (pop3). He's having this problem sending to one external domain.
I did a telnet (mail server IP) 25 and it seemed to be fine, with the same name and Ip as the MX record.
My DNSSTUFF.com account reveals that my reverse DNS seems to be ok. Any idea what the problem might be?