Strange DNS behavior for MX records...

[Mike_Harrington at bmc.com]

We are having a problem exchanging e-mail with one particular company
on the internet, while we can communicate with anyone else on the
internet without any problems at all.

While doing an nslookup on our DNS server, I can get all available
information for the company's domain, except for the MX records.
Likewise, they can get all of our information, except the MX records.
As a result, we are unable to send or receive e-mail with this
particular company.  Mail either times out, or occassionally gives a
strange error about "sender domain must exist", but not consistently.
If (within an nslookup) I set my server to anywhere else in the world,
I am able to get all information (including MX records) about either
domain.

Has anyone encountered this type of problem before, or have any ideas
as to what may be causing this problem?  Any assistance is greatly
appreciated.

- Mike Harrington -