Cannot conect to send mail

[Spirit]

Heres an over view:

I run; Exchange5.5, OutlookXP, our ISP is WorldCOM. The servers which I am attempting to send the mail are Lotus Notes.

Mail to this ONE company gets stuck in my mail queue but occasionally I can get mail through to them. They have 7 mail servers around the Globe.

I can sometimes send and receive mail but most of the time nothing will get through. Needless to say that all other mail to all other domains is fine, the addresses are correct and valid.

I can send mail direct to the Notes Servers and get a rejection notificationHi. This is the qmail-send program at ns1.company.com.
I'm afraid I wasn't able to deliver your message to the following addresses. This is a permanent error; I've given up. Sorry it didn't work out.

<Valid_User@ns1.Company.com>:
Sorry, no mailbox here by that name. (#5.1.1)



I can ping, telnet company.com mail servers fine. We are not blocked by them, they are not blocked by us, we have reverse IP lookup, they have reverse IP lookup, they're DNS is up to date and correct our DNS is up to date and correct.

Needless to say we have been emailing them for years without issue, we can send and receive to ALL other address's and the address's are spelt correctly. And of course this is our biggest customer it is happening to!

If I go into the outbound messages awaiting delivery, and look at the Details, in the Recipients <person@Company.com>[Host Unreachable]. This indecates that we cannot conect to their ISP/Servers but as explained above we can!

If I can give any info that might be helpful then please ask me for it and I shall supply. PLEEEEEEASE help.

Thx

Iain