There are many possibilities that are involved with this error. Taken from this answer of mine on another question (but slightly modified):
First, try to establish an SMTP session with the remote mail servers using telnet to see if you can gain any more information.
It’s also a possibility that some kind of oddball firewall rule has been set in place that drops, alters or otherwise tweaks packets to or from a domain or IP that is associated with the remote server. Unlikely, but I’ve seen stranger things. Check your gateway firewall as well as the Exchange server’s software firewall for any rule that could have something to do with the remote SMTP server. Check for domains, IPs and any range of addresses that could be associated with the remote domain.
Another slim possibility is that the remote domain has DNS zone issues. Maybe their MX records are stale. Perhaps they performed a zone migration but never migrated everything to the new DNS server. Again, crazier things have happened.
Yet another possibility is that the receiving server is performing a reverse DNS lookup on your sending IP and it’s not matching up with your MX records. If you MX record points to 192.0.2.1, but it’s behind the firewall that is 192.0.2.2 and a virtual IP is set up on the firewall to accept 192.0.2.1, then outbound traffic will be seen as 192.0.2.1, but RDNS will show 192.0.2.2 as the mail server. That discrepancy can cause some receiving servers to reject the message in various ways (although I would hope the recipient email admin wouldn’t suppress informative bounce messages, instead opting for generic failure messages).
(As a side note, RDNS checks like the above are foolish since many people have authenticated relays for outbound email and that, by necessity, will not match up to the inbound server. Email admins, don’t be lazy!)
Lastly, but certainly not leastly, USE SPF RECORDS! DKIM too. You may find that many of your transient email problems just disappear after properly setting up those two things.
Of course, listen to Shane Madden and check your mail queue.
In the end, contact the remote domain’s admins and work it out with them. You may have to work with them to figure the issue out.