Emails being blocked by Gmail from office 365

I have the same issue, this is not an issue with your reputation at gmail, it is not an issue with your SPF or your DKIM setup, this is an issue with the Microsoft server that is sending your email not having a DNS entry that a recieving mail server can use to verify the soruce of your email.

In a quick description of SPF, you create a record on your DNS server to let other servers know who can send emails on your behalf. When you add "spf.protection.outlook.com" to your record, you are letting other email servers know that MS can send emails on behalf of your organisation.

What is causing the issue?

1. The server recieving your email (i,e. Google) will check your SPF record
2. It then tries to resolve the address of the server that sent the email
3. The Microsoft server sending the email does not have a DNS entry
4. The recieving server then treats the email as spam
5. Goggle is nice enough to send you an email letting you know there was a problem, lots of other servers will ditch the emails and not let you know.

To verify this for your self, look in the mail header that google sent to you and try to use a reverse ipv6 DNS lookup (google for an online tool) to resolve the name for the address, if it doesn't resolve to a "protection.outlook.com" address than that is what is causing the issue.

Do mail connectors resolve the issue?

Setting up a connector for a given domain, then specifying IPv4 addresses will force Micosoft to sent the email using an IPv4 address. It just so happens that this IPv4 address resolves correctly to a protection.outlook.com address and the email is accepted as normal.

Unfortunately the described fix will only work for emails to google, you will need to find all the domains that are failing to accept your emails and setup a connector for each. We have about 40 odd connectors to use for customers that are using google to host their email.

How do I know when my emails are being denied?

There is a service provided by Valimail which can collect and analyse email delivery, no affiliation, just a great tool.

How do we fix it?

Provide this information to your MS service rep, if they tell you to modify your SPS or DKIM records, ask them to escalate your call to an engineer or someone who understands that Microsoft is the only one who can fix this issue as they are they ones that publish the DNS records for their servers.

The problem seems to be fixed!

Every so often your tenant is rotated to a new email server, if you happen to get assigned to one where the DNS address is correctly published, then everything works as normal again, the only problem is you will eventually be rotated back to the server with the bad DNS configuration and all the problems come back. This happened to me, took down all the connectors, then a week later all the emails started failing again.

This is an awesome answer but way above my pay grade for putting into practice.

I have the same problem. Its all Gmail recipients and is a major problem for our law firm over the past month or so.

Have also the same problem, Im using a @outlook.ph domain, Gmail blocked/rejected every messages I sent regardless whether I used app, web or mobile. The issue was started around mid March 2023.

The full text of the coming from postmaster is:

mx.google.com rejected your message to the following email addresses:

*** Email address is removed for privacy *** (*** Email address is removed for privacy ***)Your message couldn't be delivered because the recipient's email server (outside Office 365) suspected that your message was spam. To fix this, try to modify your message, or change how you're sending the message, using the guidance in this article: E-mailing Best Practices for Senders. Then resend your message. If you continue to experience the problem, contact the recipient by some other means (by phone, for example) and ask them to ask their email admin to add your email address or your domain name (the text after the "@" symbol in your email address) to their allowed senders list.

For Email Admins
When Office 365 tried to send the message to the next email server outside of Office 365 the external email server returned the error below. This indicates the recipient's email server (or their email filtering service) suspected the sender's message is spam. If the sender isn't able to fix the problem by modifying their message then contact the recipient's email admin and ask them to add your domain name, or the sender's email address, to their list of allowed senders.

While the sender may be able to alter the message contents to fix this, it's likely that only the recipient's email admin can fix this problem. Unfortunately, Office 365 support is unlikely to be able to help fix these kinds of externally reported errors.

mx.google.com gave this error:Remote server returned message detected as spam -> 550 5.7.1 [2a01:111:f403:7005::802 19] Our system has detected that this;message is likely suspicious due to the very low reputation of the;sending domain. To best protect our users from spam, the message has;been blocked. Please visit; https://support.google.com/mail/answer/188131 for more information. ka7-20020a170907990700b0094f54c032dbsi7178285ejc.154 - gsmtp

Another way that I have found is that knowing that gogle has blocked IPV6, as dapg_032 rightly says, you have to look for the ipv4 with mxtoolbox from O365 and instead of creating a connector for each domain that gmail blocks, including workspaces, you can modify the SPF and add the ipv4 so that it checks with the IPV6 . By doing that, any mail that goes to a google sender goes through. It works for me.

This is the SPV that I have configured for O365

v=spf1 ip4:40.92.0.0/15 ip4:40.107.0.0/16 ip4:52.100.0.0/14 ip4:104.47.0.0/17 -all

I hope it helps you.