DNS question

I manage the mail server (mail.ourcompany.com) at my company. We provide mail services to a number of clients.

Today CompanyA calls in and reports that CompanyB tried to send them an email, but they never recieved it. According to CompanyB, the mail left there outbox.

The two addresses involved are: bob@companyA.com and john@companyB.com

Our DNS server are authoritive for companyA.com and dns.fakedomain.com are authoritive for companyB.

I "lserver" to dns.fakedomain.com and do a lookup for our mail server: mail.ourdomain.com

The DNS request times out.

But i can ping there DNS server fine...

What is happening? Do they not have an entry on there DNS servers for our domain??

If they dont, what is the process for getting there DNS servers to recognize ours? Is there some kind of prompt-type signal you can send? Or do i have to just physically phone the guys and say: "Hello, please add an entry for our domain..."

Help

It does look like there is something is wrong with their DNS. The only thing that you can do is inform the Sys Admin!