All External Mail to Office 365 Fails SPF, Marked as Junk by EOP in a Hybrid Deployment

In short: legitimate emails are landing in Junk folders as EOP (Exchange Online Protection) stamps email messages as junk (SCL5) and SPF-failed. This happens with all external domains (e.g. gmail.com/hp.com/microsoft.com) to client’s domain (contoso.com).

Background info:

We are at the beginning of migrating mailboxes to Office 365 (Exchange Online). This is a Hybrid Deployment/Rich-Coexistence configuration, where:

• On-Premises = Exchange 2003 (Legacy) & 2010 (Installed for Hybrid Deployment)
• Off-Premises = Office 365 (Exchange Online)
• EOP is configured for SPF checking.
• MX records are pointing at the on-premises as we haven't completed migrating all mailboxes from on-premises to Exchange Online.

The problem is when external users sends emails to an Office 365 mailbox in the organization (mail flow: External -> Mail Gateway -> on-premises mail servers -> EOP -> Office 365), EOP performs an SPF lookup and hard/soft failing messages with the external facing IP address of the Mail Gateway from which it received the mail.

(On-premises mailboxes do not show this problem; only mailboxes migrated to Office 365 do.)

An illustration:

Example 1: from Microsoft to O365

Authentication-Results: spf=fail (sender IP is 23.1.4.9) 
smtp.mailfrom=microsoft.com; contoso.mail.onmicrosoft.com;
dkim=none (message not signed) header.d=none;
Received-SPF: Fail (protection.outlook.com: domain of microsoft.com does not designate
23.1.4.9 as permitted sender) receiver=protection.outlook.com; client-ip=23.1.4.9; 
helo=exchange2010.contoso.com; X-MS-Exchange-Organization-SCL: 5

Example 2: from HP to O365

Authentication-Results: spf=none (sender IP is 23.1.4.9) 
smtp.mailfrom=hp.com; contoso.mail.onmicrosoft.com; dkim=none 
(message not signed) header.d=none; Received-SPF: None 
(protection.outlook.com: hp.com does not designate permitted sender hosts) 
X-MS-Exchange-Organization-SCL: 5

Example 3: from Gmail to O365

Authentication-Results: spf=softfail (sender IP is 23.1.4.9) 
smtp.mailfrom=gmail.com; contoso.mail.onmicrosoft.com; 
dkim=fail (signature did not verify) header.d=gmail.com; 
Received-SPF: SoftFail (protection.outlook.com: domain of transitioning 
gmail.com discourages use of 23.1.4.9 as permitted sender)  
X-MS-Exchange-Organization-SCL: 5

For message headers with X-Forefront-Antispam-Report, refer to http://pastebin.com/sgjQETzM

Note: 23.1.4.9 is the public IP address of the on-premises hybrid Exchange 2010 server connector to Exchange Online.

How do we stop external emails from being marked as junk by EOP during coexistence stage of a Hybrid Deployment?

[2015-12-12 Update]

This issue was fixed by the Office 365 support (the escalated/backend team) as it has nothing to do with our settings.

We were suggested the follows:

1. Whitelist the public IP in EOP Allow List (Tried. It did not help.)
2. Add SPF record for our domain: "v=spf1 ip4:XXX.XXX.XXX.XXX ip4:YYY.YYY.YYY.YYY include:spf.protection.outlook.com -all" (Don't think this suggestion is valid as EOP should not check gmail.com against our SMTP IP address as it is not specified in the SPF records of gmail.com. That does not seem the way SPF works.)
3. Make sure TLS is enabled (See below)

The key part is the third point. "If the TLS is not enabled, incoming email from local Exchange will not be marked as internal/trust email, and EOP will check all records," said the support.

The support determined a TLS issue from our mail headers by the below line:

• X-MS-Exchange-Organization-AuthAs: Anonymous

This indicates TLS was not enabled when EOP received email. EOP did not treat the incoming email as trust email. The correct one should be like:

• X-MS-Exchange-Organization-AuthAs: Internal

However, this was not caused by our settings; the support person helped us make sure our settings were correct by verifying the verbose SMTP logs from our Exchange 2010 Hybrid server.

At around the same time, their backend team fixed the problem without letting us know what exactly caused it (unfortunately).

After they fixed it, we found that the message headers had some significant changes as below.

For internal-originated mail from Exchange 2003 to Office 365:

• X-MS-Exchange-Organization-AuthAs: Internal (It was "Anonymous")

• SCL=-1 (It was SCL=5)

• Received-SPF: SoftFail (It was the same)

And for external mails (e.g. gmail.com) to Office 365:

• X-MS-Exchange-Organization-AuthAs: Anonymous (It was the same)

• SCL=1 (It was SCL=5)

• Received-SPF: SoftFail (It was the same)

Although SPF check still soft-fails for gmail.com (external) to Office 365, the support person said it was OK, and all mails would go to the Inbox instead of Junk folder.

As a side note, during troubleshooting, the backend team found one seemingly minor configuration issue -- we had the IP from our Inbound Connector (i.e. public IP of Exchange 2010 Hybrid server) defined in our IP Allow List (suggested by another Office 365 support person as a troubleshooting step). They let us know we should not need to do this and in fact doing so can cause routing issues. They commented that on initial pass the email were not getting marked as spam so there was also a possible issue here. We then removed the IP from the IP Allow List. (However, the spam issue existed before the IP Allow List setting was made. We didn't think Allow List was the cause.)

In conclusion, "it should be EOP mechanism," said the support person. Therefore, the whole thing should be caused by their mechanism.

For anyone interested, the troubleshooting thread with one of their support persons can be viewed here: https://community.office365.com/en-us/f/156/t/403396

Are you sure mail flow is going directly from your Hybrid server to O365?

When you ran the hybrid wizard it should have created connectors locally and in O365, which will tread mail flow between the forests as internal mail. This means it will bypass the EOP/Spam checks and you should never see those SPF messages.

If your edge device is modifying the headers this may be causing your issue - between your server and O365 nothing should modify the message headers. Make sure you don't have an existing connector that may be overriding the ones created by the Hybrid wizard. You can always delete the existing connectors that were created and re-run the wizard to re-create them.

Check your transport rules in Exchange and make sure they are not modifying the message before going to O365, if they are disable them and test again to make sure those are not your problem.

Last (or maybe first) check that your federation is configured correctly. If it's not that could be why your mail is not treated correctly. This is where re-running the Hybrid wizard can you help you as well.

Not an expert here, it's been a very long time since I played with Exchange but I'll try to answer to the best of my ability.

Lets discus the design for a second, why don't you route all traffic to EOP first and then to your in-premises Exchange servers? you're losing a good functionality there, it would definitely make things easier for you to control spam from a single location (assume that you're local Exchange has an anti spam filter too).

Now lets move to the spam problem:

1. Mail Flow and Connectors: I have a feeling that the connectors are not setup correctly, if all of your incoming emails appears to be originated from the same 23.1.4.9 IP address instead of the senders mail server IP address, for sure SPF checks would fail, since the purpose of it is to check the sender IP and the domain name of that sender IP. I would definitely spend some time on reviewing how the connectors are setup, here's a good link for that: https://technet.microsoft.com/en-us/library/ms.exch.eac.connectorselection(v=exchg.150).aspx
2. EOP Spam Filters and Connection Filters: if the IP setup of the connectors is done correctly, perhaps its time that you look at your spam/connection filters under EOP, I'd create filters to bypass checking incoming emails from the IP 23.1.4.9, but that would make all incoming emails bypass the spam filter check lists, this brings you to the problem mentioned in the previous point, check your connectors and preferablly, route incoming email to EOP first.