Exchange server 2003:
ESM, Servers, <your server>, Protocols, SMTP. Right click on the Default SMTP vs and choose Properties. Click on Delivery and then Advanced. In the FQDN box enter what your server is known as on the internet – mail.domain.com for example. 

If you have an exchange server running on dynamic IP address and you domain name is not mapped to this server you can get this error also.