email can't be delivered to valid recipient address

Hello. I have a problem with email to a business partner that we have been sending stuff to for years but suddenly all our email is bounced back as non-deliverable. I have been talking with them and they say nothing has changed of their end. Nothing has changed on our end for certain. It's only email from us to them that gets rejected (tested with yahoo email and it works fine) and we are able to recieve from them. Has anyone run into a similar situation before?

We have microsoft exchange 2000 (latest SP and patches). The smtp message queue properties say that a smtp protocol error has occuredd but donesn't specify any additional info. Below are copies of the error messages I have received while testing:

 The destination server for this recipient could not be found in Domain Name Service (DNS).  Please verify the email address and retry.  If that fails, contact your administrator.
            <ubgexchange.unitybuilders.com #5.4.0>

Could not deliver the message in the time limit specified.  Please retry or contact your administrator.
            <ubgexchange.unitybuilders.com #4.4.7>

The e-mail system was unable to deliver the message, but did not report a specific reason.  Check the address and try again.  If it still fails, contact your system administrator.
            <ubgexchange.unitybuilders.com #4.0.0 smtp;417 DNS lookup failure: unitybuilders.com.  Try again later.

Any ideas?
SirTravis