Look in the protocol logs to see the actual conversation your own server(s) have with the recipient's domain. Since there were interesting side-notes with the FQDN, at least in Exchange Server 2010 (FQDN section
in this article), it might be best to looks at resulting conversation, instead of individual settings. Verbose logging should be set against the connector used to send mails to Internet (Get-Sendconnector | ft Name, AddressSpaces, Fqdn, ProtocolLoggingLevel
will provide if this is already set). Next the path of the logs can be extracted from all source servers used for that send connector using Get-TransportService <MailboxServer> | fl SendProtocolLogPath. Once inside things should be pretty clear
once the EHLO line your own server is sending is identified.
Last and not least - is there only a handful of recipient organizations refusing messages or the majority of them ? If 1-2, then it could be the recipient's systems or the RBL providers (including PTR checks for your sending host) that might be having
issues.