Exchange 5.5 and Host unreachable

Hi,

I’ve a problem with Host unreachable. When I send mail to a specific domain, I’ll get a NDR saying host unreachable. The recipient at the domain I’m trying to send to can’t send to our domain either.
I’ ve tried telnetting their mail serverand to send mail through that way and it works. MS Knowledgebase article 153119.
This is the reciept mail get from them:
Final-Recipient: RFC822; info@bohusbetong.se
Action: relayed (to non-DSN-aware mailer)
Status: 2.0.0
Remote-MTA: DNS; mail3.ports.se
Diagnostic-Code: SMTP; 250 Accepted
Last-Attempt-Date: Mon, 23 Jun 2003 10:13:19 +0200

Any suggestions on how to solve this problem?

Regards
//H