2562 error to one domain

We are having trouble emailing just to one particular domain. The error log shows below and even though the last line says "transferred 1 message … " the other company is not receiving the email. I am able to telnet to their mail server, I tried different dns servers. Nothing helped so far. They say they are not having issues receiving email from any other domains. Any thoughts on this ?

01/20/2009 02:27:13 PM [0B5C:0007-0ABC] SMTPClient: Attempting to Connect: Host mx.superb.net, Port 25, SSL Port 0, Connecting Domain mail.mycompany.com

01/20/2009 02:27:13 PM [0B5C:0007-0ABC] SMTPClient: Connection successful

01/20/2009 02:27:15 PM [0B5C:0007-0ABC] SMTPClient: ReceiveResponse: 220 ESMTP

01/20/2009 02:27:15 PM [0B5C:0007-0ABC] SMTPClient: CommandEHLO: EHLO mail.mycompany.com

01/20/2009 02:27:15 PM [0B5C:0007-0ABC] SMTPClient: ReceiveResponse: 250-

01/20/2009 02:27:15 PM [0B5C:0007-0ABC] SMTPClient: ReceiveResponse: 250-PIPELINING

01/20/2009 02:27:15 PM [0B5C:0007-0ABC] SMTPClient: ReceiveResponse: 250-8BITMIME

01/20/2009 02:27:15 PM [0B5C:0007-0ABC] SMTPClient: ReceiveResponse: 250-SIZE 31457280

01/20/2009 02:27:15 PM [0B5C:0007-0ABC] SMTPClient: ReceiveResponse: 250 AUTH LOGIN PLAIN CRAM-MD5

01/20/2009 02:27:15 PM [0B5C:0007-0ABC] SMTPClient: SMTP Authentication is not required by local server. Username: -blank-

01/20/2009 02:27:15 PM [0B5C:0007-0ABC] SMTPClient: Attempting to SubmitMessage:

01/20/2009 02:27:15 PM [0B5C:0007-0ABC] SMTPClient: Pipelined commands:

01/20/2009 02:27:15 PM [0B5C:0007-0ABC] SMTPClient: MAIL FROM:user@mycompany.com SIZE=3122

01/20/2009 02:27:15 PM [0B5C:0007-0ABC] SMTPClient: RCPT TO:purchasing@othercompany.com

01/20/2009 02:27:15 PM [0B5C:0007-0ABC] SMTPClient: DATA

01/20/2009 02:27:15 PM [0B5C:0007-0ABC] SMTPClient: End of pipelined commands

01/20/2009 02:27:15 PM [0B5C:0007-0ABC] SMTPClient: ReceiveResponse: 250 ok

01/20/2009 02:27:15 PM [0B5C:0007-0ABC] SMTPClient: ReceiveResponse: 421 Temporary error (#4.3.0)

01/20/2009 02:27:15 PM [0B5C:0007-0ABC] SMTPClient: CommandRSET:

01/20/2009 02:27:15 PM [0B5C:0007-0ABC] SMTPClient: Attempting to Disconnect:

01/20/2009 02:27:15 PM [0B5C:0007-0ABC] SMTPClient: CommandQUIT:

01/20/2009 02:27:15 PM [0B5C:0007-0ABC] SMTPClient: Connection terminated with status: 2562

01/20/2009 02:27:15 PM Router: Transferred 1 messages to othercompany.COM (host mx.superb.net) via SMTP