The problem exists at the recipient's mail servers, not on your end. Check the remote domains' MX records and make sure that their mail servers are responding to SMTP requests. 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 0.0.0.1, but it's behind the firewall that is 0.0.0.2 and a virtual IP is set up on the firewall to accept 0.0.0.1, then outbound traffic will be seen as 0.0.0.1, but RDNS will show 0.0.0.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.
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.