We are able to send email to all OTHER external domains, with no issue.
"Company A" is one of our clients. We are unable to send emails to "Company A"
"Company B", another one of our clients, can successfully send email to "Company A"
"Company C", a client of "Company A" is unable to send emails to "Company A"
There are at least 3 known domains that can not send email to "Company A", all other domains work fine.
When we attempt to send to "Company A", our exchange 2007 server eventually kicks back the following error: #550 4.4.7 QUEUE.Expired; message expired ##
Using telnet to connect to the MX address of Company A, on port 25:
My Mail Server & Office ISP (Time Warner) - FAIL
My Office computer & ISP (Time Warner) - FAIL
My Home computer & ISP (AT&T U-Verse) - FAIL
From my phone (Android, on Work Wi-Fi (TW)) - FAIL
From my phone (Android, on Verizon) - SUCCESS
"Company D" (Adams Wells) - SUCCESS
"Company E" (Cincinnati Bell) - SUCCESS
On all of the above, I am able to correctly resolve the DNS of their MX entry.
MXtoolbox.com's diagnostics can successfully connect to "Company A".
I'm running out of ideas on where to look to try an isolate this issue. As I said, there are other companies who are also unable to send to Company A, so it's not necessarily something wrong on my exchange server.
I've tried to provide as much technical information as possible.
Thank you for your time, and suggestions.