Could be a number of things. Where did you try to send the mail from for it to be received by the server? Was it from outside the server or from within the server itself?
 
If from outside the server using a regular email provider account - it could be that the reverse for the Exchange Server is not working properly.
- or it could be that your backbone provider is blocking certain types of traffic or ports required for Exhange to recieve mail or respond to reverse lookups by external servers for mail traffic
 
I would suggest extensive port and traffic testing
Also analyze your firewall and server logs
 
Also you may find this link helpful
http://www.zoneedit.com/smtp.html?ad=lookup
Hope this helps

Just doing a few checks with the tool you had provided, I am able to receive those test emails. I am not however able to send directly to this domain. If you have any more ideas or suggestions they would be greatly appriciated.
 
 
Thanks,
 
 
The eternal newbie.....

So you tried the SMTP test and the pop3 test link as well? Were these tried from an external computer or from the server? Best to use an external computer. That way you will be able to see the results of what the problem is.
 
Was anything displayed on the test results for the one that failed?

Both were tried from a computer outside of the network. On a different ISP. Both tests showed no problem.
 
 
The eternal newbie.....