email being delayed from one domain

its possible DNS issue ... look here :

http://support.microsoft.com/kb/329636
and here :

http://exchange.sembee.info/2003/smtp/smtp-connector.asp

We are using dns to route. The strange thing is that we were able to send to this domain without issue until two days ago. Could it be something they did on their end? They are using an Exchange server as well.

see here :

https://www.experts-exchange.com/questions/20993899/Delivery-to-the-following-recipients-has-been-delayed.html

Hi,

This may occur due to the outbound security of the Simple Mail Transfer Protocol (SMTP) virtual server or the outbound security of one or more SMTP Connectors are set incorrectly.

Verify your settings from the below mentioned link.

http://support.microsoft.com/kb/329636

http://social.technet.microsoft.com/Forums/en-US/exchangesvrtransport/thread/43be2842-3da4-489a-b035-ab01ac5f3dc2/

Hope this information will be useful.

Quick test that will more than likely produce the issue.   Get the MX record of the recipient system...then attempt to telnet over smtp to that server and see what you get.    Basically from a command prompt on your exchange box or smtp gateway:   telnet mxdnsofrecipient 25   you can then attempt to send mail via telnet if you connect to see if you get a reject message from their message hygiene or someother disconnect notice...that is if you connect.

do you have firewall installed? its possible its drop the connection which is caused timeout

This is 100% a DNS issue, it's nothing to do with firewall (jordannet seriously?) Perform the telnet test as stated above and review your DNS infrastructure. I would assume your Exchange server is using your AD DNS which in turn is forwarding to your ISP, or your AD might be using Root Hints instead.

From a command prompt, type NSLOOKUP

Microsoft Windows [Version 6.1.7601]
Copyright (c) 2009 Microsoft Corporation.  All rights reserved.

C:\Users\radweld>nslookup
Default Server:  tank.rs2v.local
Address:  192.168.0.4

> set type=mx
> contoso.com
Server:  tank.rs2v.local
Address:  192.168.0.4

Non-authoritative answer:
contoso.com     MX preference = 10, mail exchanger = mail.global.frontbridge.com

mail.global.frontbridge.com     internet address = 94.245.120.86
mail.global.frontbridge.com     internet address = 216.32.181.178
>

If you cant resolve the MX then look at your DNS, Basically which ever way your using, try the other. If your using a forwarder, remove it and enable Root Hints or if your using root hints, remove them and use a forwarder.

One other possibility is your on a DNS black list and the receiving server is denying connections. However i suspect you are unable to resolve the address.

Forgot to add, it's best practice for MX records to resolve to a hostname which then is resolved back to the destination exchange server. If you can resolve the MX record, then set the type back to A and ensure the A record resolves to the same IP as those listed in the MX checks.

Microsoft Windows [Version 6.1.7601]
Copyright (c) 2009 Microsoft Corporation.  All rights reserved.

C:\Users\tony.hill>nslookup
Default Server:  tank.rs2000-16v.local
Address:  192.168.0.4

> set type=mx
> contoso.com
Server:  tank.rs2000-16v.local
Address:  192.168.0.4

Non-authoritative answer:
contoso.com     MX preference = 10, mail exchanger = mail.global.frontbridge.com


mail.global.frontbridge.com     internet address = 94.245.120.86
mail.global.frontbridge.com     internet address = 216.32.181.178
> set type=a
> mail.global.frontbridge.com
Server:  tank.rs2000-16v.local
Address:  192.168.0.4

Non-authoritative answer:
Name:    mail.global.frontbridge.com
Addresses:  94.245.120.86
          216.32.181.178

If the recipient messaging system is denying connections from the sending messaging system will produce the same delay messages.     Which is why I recommend testing SMTP connectivity test from the sending system.    Basically lookup the MX record using http://www.mxtoolbox.com/  then take that DNS MX record and run the telnet test from your server.   Also ping the MX record from your system to see if it resolves the same IP.    Yes it may be a DNS issue...but these steps should point you in the correct direction.

I am unable to ping or telnet from the server or anywhere else. The ip does resolve on the server. The users had previously been sending emails to this address for the last few years. They can send out to them through their iphones.

try to ping 8.8.8.8
is there any reply?

yes

To  make this a bit easier...what is he mail server you are attempting to send to?   what is the domain?