sendmail error 503 5.0.0 Need MAIL befor

Hi

I am not familiar with sendmail at all (I am a Microsoft Exchange
Administrator) so I really need some help from you experts. My
company is not able to send to another company that uses sendmail as
their e-mail platform. We receive the following bounce back message
when mailing to them:

Unexpected recipient failure - 503 5.0.0 Need MAIL before RCPT

The sendmail e-mail administrator swears that there is not a problem
with his server and that it's a problem on my side yet I sent them the
dialog that my e-mail server had with his and the dialog states that
the message was passed to his e-mail server.

Now I don't understand how sendmail resolves but I'm guessing that
these people don't have the 'accept_unresolvable_domains' enabled on
their sendmail server and their server is not resolving my domain. If
this is the case, how does sendmail resolve a domain? Does it only
use DNS recors? I ask because my domain is configured not to reply to
ping requests for security reasons. I am not aware of any DNS
misconfigurations with any ISPs in regards to my company.

Funny thing is that the sendmail administrator rebooted his sendmail
server the other day and things were temporarily fixed for a day. Now
the problem is back again.

Can anyone give me some advice on what I should do to troubleshoot
this? I'm really frustrated that the sendmail administrator is making
this my problem and does not have any knowledge on how to troubleshoot
this problem.

Thanks,

Rebekah