Emails sent to your Exchange Online mailboxes may be delivered to the Junk Email folder of Outlook, and modified with the following message in the email body:
This sender failed our fraud detection checks and may not be who they appear to be. Learn about spoofing at http://aka.ms/LearnAboutSpoofing
If you know that the email is legitimate, and is not a spoofed email, the cause of the issue may be an incorrectly configured Sender Policy Framework (SPF) record that does not specify the IP address of the server or host that sent the junked email as an allowed sender.
Update, March 2018 – I originally wrote this article to address what was a minor issue that mostly impacted domain owners' emails to themselves. For example, email notifications sent from an external website or SaaS application to your internal users, using your own domain. As of early 2018, changes to Office 365 ATP are resulting in a high rate of these false positives due to more aggressive filtering of email that fails domain authentication checks (SPF, DKIM, DMARC, and other signals that ATP users). Read more here.
Fixing Your Own SPF Record
When you add an email domain to your Office 365 tenant Microsoft presents an SPF record that they recommend be added to your public DNS zone. The SPF record is created as a TXT record, and will look similar to this:
v=spf1 include:spf.protection.outlook.com -all
The default SPF record nominates Microsoft's servers that handle outbound email for Exchange Online as permitted senders for your domain. All other IP addresses on the internet that try to send email using your domain will fail the SPF check, and if SPF lookups are being used to prevent spam, spoofing, and phishing attacks (as they are in Exchange Online Protection), the email will be rejected or junked as shown in the example above.
However, it's quite normal for businesses who use Office 365 for email to have other sources of email for their domain, such as the web server that hosts their public-facing website, or a SaaS application (such as payroll, marketing, or monitoring systems) that sends email “From” the domain. It isn't always necessary to add the host names or IP addresses for external systems to your SPF record, depending on how they send email. For example, if you have an external application using Amazon SES for SMTP, adding Amazon SES to your SPF record isn't always required. In many cases you'll have no control over how the external system sends email though, and adding them to your SPF record will be necessary.
In the example message shown at the start of this article, the SPF check failed because the host sending the email is not in the SPF record. This can be seen by viewing the message headers of the junked email.
The headers can be difficult to read, so you may need to copy and paste them into the message analyzer in the Microsoft Remote Connectivity Analyzer. Look for the “Received-SPF” header.
For third party systems and SaaS applications you should check with their technical support to see whether they provide any advice as to what you should add to your SPF record. Often they'll provide an IP address, range of IPs, or a specific host name. If they don't provide advice, or if you control the server that is sending the emails and already know the IP address, you can go ahead and add the IP to your SPF record. For this example, the IP 18.104.22.168 needs to be added, so the original SPF record would be updated as follows:
v=spf1 ip4:22.214.171.124 include:spf.protection.outlook.com -all
There are other mechanisms for configuring SPF records. If you need assistance building an SPF record for your domain try SPF Wizard. Just be sure to maintain the “include:spf.protection.outlook.com” that is required for Exchange Online.
After updating your SPF record and waiting for the old record to expire from DNS caches, your emails should deliver successfully to inboxes without being junked by Exchange Online Protection.
To learn more about SPF, read my SPF primer for Exchange admins.
Fixing Someone Else's SPF Record
Since you have no control over other the DNS records for other peoples' domains, you can't directly fix a problem with their domain authentication. If you're seeing a high rate of false positive junk mail for another domain, and you believe that the issue is caused by their SPF implementation, you should start by getting in contact with their email administrators.
That can be a challenge if you don't have their contact details, or if they outsource their support to a third party. Sometimes it's necessary to get in touch with the person who sent the email that was junked, then ask them to escalate the matter internally to their help desk, or provide you with the contact details. Even then, the conversation can quickly turn into a finger pointing exercise where the domain owner doesn't want to take responsibility for fixing their domain authentication issues.
If it helps, point them at this advice from Microsoft, particularly this quote:
The newest anti-spoof features help protect organizations from external domain spoof. Office 365 honors emails from external domains having proper SPF, DMARC, and DKIM authentication settings enabling them to pass authentication, and junks messages that fail this authentication. The challenge occurs when external domains do not have these settings properly configured…. (We recommend) admins of sender domains into Office 365 update SPF, DKIM, DMARC configurations so emails can pass the stricter authentication rules.
The longer the other domain owners ignore the problem, the worse the situation will get for them. If they want to reliably send to Office 365 customers, they'll need to fix their domain authentication problems. Eventually, their own users may end up putting enough pressure on them to fix the problem.