I'm working through a beast of an issue at the moment.

• Exchange 2010 single server on prem
• Hybrid deployment to Office 365
• ESMTP filtering turned off on ASA

Certain domains (most consistently, Hotmail/Live) cannot send us mail. At one point, we couldn't send out either, but I created a new Send Connector that forces HELO instead of EHLO.

I turned on SMTP logging, an example of the failed inbound message connection is below. I've read that it could be that reverse DNS is the problem, i.e., the exchange banner smtp address needs to reverse-DNS back to the same IP. Since it's the default exchange connector, its banner is the server's name, but the DNS name of the MX record is different. I'm waiting for the PTR records to update to reflect the internal name as well.

Is that the right direction? Is this all DNS or something different?

SMTP Session Log (single failed session for illustration):

SMTPSubmit SMTPAcceptAnySender SMTPAcceptAuthoritativeDomainSender AcceptRoutingHeaders
220 ExchangeServerName.internalSubDomain.example.com Microsoft ESMTP MAIL Service ready at Mon, 15 Oct 2012 09:57:24 -0400
EHLO col0-omc3-s4.col0.hotmail.com
250-ExchangeServerName.internalSubDomain.example.com Hello [65.55.34.142]
250-SIZE
250-PIPELINING
250-DSN
250-ENHANCEDSTATUSCODES
250-STARTTLS
250-X-ANONYMOUSTLS
250-AUTH NTLM LOGIN
250-X-EXPS GSSAPI NTLM
250-8BITMIME
250-BINARYMIME
250-CHUNKING
250-XEXCH50
250-XRDST
250 XSHADOW
MAIL FROM:<[email protected]>
08CF5268DABBD9AA;2012-10-15T13:57:24.564Z;1
250 2.1.0 Sender OK
RCPT TO:<[email protected]>
250 2.1.5 Recipient OK
XXXX 1282 LAST
Tarpit for '0.00:00:05'
500 5.3.3 Unrecognized command
XXXXXXXXX from COL002-W38 ([65.55.34.135]) by col0-omc3-s4.col0.hotmail.com with Microsoft SMTPSVC(6.0.3790.4675);
Tarpit for '0.00:00:05'
500 5.3.3 Unrecognized command
"    XXXX 15 Oct 2012 06:57:24 -0700"
Tarpit for '0.00:00:05'
500 5.3.3 Unrecognized command
XXXXXXXXXXX <[email protected]>
Tarpit for '0.00:00:05'