Today, I found myself working with a customer that was experiencing delivery failures to some Office 365 recipients from all external senders.
As problems go, this one definitely finds itself in the “interesting” category. No, it’s never good to have “interesting” problems (just ask a doctor).
- MX record points to on-premises spam gateway, which delivers to on-premises Exchange 2013 environment
- All mailboxes were hybrid migrated to Office 365
- Azure AD Connect is synchronizing identity
- Inbound mail from external senders was not being delivered to some cloud recipients, though the same cloud recipients could send external mail and could send/receive with internal users.
Ran through the normal troubleshooting:
- on-premises Exchange receive connector is listening on port 25
- mail gateway log say ‘delivered’ to Exchange server
- Exchange server has valid 3rd-party certificates bound
- recipients have the correct type, depending on if they are new or migrated mailboxes
- recipients in Exchange have tenant.mail.onmicrosoft.com proxy address
- recipients in Exchange have valid target address pointing to the correct tenant.mail.onmicrosoft.com proxy
- on-premises Exchange server can contact tenant-onmicrosoft-com.mail.protection.outlook.com on port 25
- Hybrid Configuration Wizard was run successfully
Enabled protocol logging, restarted the transport service, and decided to start investigating more deeply.
I discovered this snippet in the Send log:
MAIL FROM:<firstname.lastname@example.org> SIZE=264118
RCPT TO:<email@example.com> ORCPT=rfc822;firstname.lastname@example.org
250 2.1.0 Sender OK
550 4.3.1 Recipient address rejected: Access denied. AS(201806281) [XXXXXXXXXXX.eop.prod.protection.outlook.com]
The message is getting to Exchange Online, but it is being rejected. 550 is generally a “mailbox not found,” but the status code is … interesting, as we know the mailbox exists and can successfully conduct internal transactions.
In this case, the temporary solution was disabling Directory-Based Edge Blocking (DBEB) by changing the customer domains (not the onmicrosoft.com ones) in Exchange Online to InternalRelay.
The larger problem was caused by some on-premises Active Directory issues that were synchronized via AAD Connect. Each affected object needed to be updated (in essence, removing and re-adding SMTP addresses) to ultimately resolve the issue.