Time to time, I see situations, when Exchange unable to send some emails to some organisations. In most cases, there is not a problem on Exchange level. Very often, it’s is DNS issues. If you check your logs, you can find there some events with similar content:
The DNS server encountered an invalid domain name in a packet from 216.113.128.62. The packet will be rejected. The event data contains the DNS packet.

Here is a solution that works for me :).

Check following registry key and value set for it:

HKEY_LOCAL_MACHINE\System\CurrentControlSet\Services\DNS\Parameters\DisableAutoReverseZones

According to KB 198410 it should have a non-zero value
The packet was forwarded to non-recursive DNS server. I will recommend switch to forwarders for few days to check if that helps.
The server is querying for DNAME record, which is not supported. Responses containing DNAME (rrtype – 0×0027) record.
Extended DNS (EDNS) packets are received but the server that is attempting to resolve the EDNS traffic doesn’t support EDNS or have it enabled. An easy workaround is to disable EDNS.

dnscmd /Config /EnableEDnsProbes 0