Unable to deliver due to a communications failure

[InfoArtist]

Hello:

Messages to a certain Internet address (e.g., joe@company.com) are returned by Exchange as "unable to deliver the messagedue to a communications failure."

What is interesting is this: if I run an nslookup on company.com, I can't find an A or MX records, so I can understand why Exchange has a communications failure.

But, if I ping company.com or go to

http://company.com,

it works. Also, if I telnet company.com on port 25 I get a response from an SMTP server.

Is Exchange resolving domain names differently than other applications? How can this be controlled or debugged?

Thank you!