Question : The recipient was unavailable to take delivery of the message

Hello,
I have Exchange 5.5 running on a 2K server.  We started doing business with another company, but we cannot email them.  We can receive emails from them but cannot reply.  The error that comes back is:

Your message did not reach some or all of the intended recipients.

      Subject:      Test
      Sent:      8/29/2006 7:03 PM

The following recipient(s) could not be reached:

      [email protected] on 8/29/2006 7:03 PM
            The recipient was unavailable to take delivery of the message
      The MTS-ID of the original message is: c=US;a= ;p=Administration i;l=SERVER-060830000322Z-3650
            MSEXCH:IMS:Organization.:DOMAIN:SERVER 3554 (000B09AA) 554 cgimta001.ottawatechops.com

We haven't had any problems with any other email.  My boss is getting pretty ticked because we can't give him an answer.  Any help would be much appreciated!
Thanks!
CB

Answer : The recipient was unavailable to take delivery of the message

Looks like the receiving end is bouncing your messages for some reason. Try to mail them from hotmail or similar. Also try to mail them from a Telnet Session: http://www.yuki-onna.co.uk/email/smtp.html. Finally, speak to their mail responsible person and work with him to pinpoint the problem. They might have something on their side to block you for some reason, maybe a spam blocking company like http://www.spamhaus.org, your company might be listed there, search your IP address undes SPL & XBL.

Regards
Peter