Microsoft 365 emails to Gmail getting blocked with 550 5.7.1 errors

 We are using Microsoft 365 for their email service and recently faced an issue where outgoing emails to Gmail were not getting delivered because of the following error :

550 5.7.350 Remote server returned message detected as spam -> 550 5.7.1 [2a01:111:f403:c40f::7 19] Gmail 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. For more information, go to; https://support.google.com/mail/answer/188131 d9443c01a7336-220d5320c49si112823045ad.160 - gsmtp

Now unless you have some kind of gold-star support with either Microsoft or Gmail, you are stuck with combing through documentation and forums to understand where to even start troubleshooting this error. The usual steps of checking if the domain is listed on spam sites (MultiRBL) and if TestExchangeConnectivity didnt give much insight into the error.

After an hour of going through various forum posts, there was a set of posts with a workaround for a similar situation of emails being sent from Microsoft 365 servers. 

The issue that was identified was that Gmail was blocking emails sent to their servers from IPV6 addresses which were used by Microsoft, as these IPs were not listed on the SPF record of the domain sending the email. 

Now Microsoft documentation recommends to add "include:spf.protection.outlook.com" to the domain SPF record. And technically it "should" resolve to all the outgoing IPs of Microsoft . But I assume in this case the IPv6 server IPs are not resolved here, and so it gets blocked

The rule was to filter emails sent to gmail.com or *.gmail.com and the option to select was the MX record option. The idea here was that DNS resolution using the MX record would force resolution in IPV4 and everything will go well. 
So I setup the rule, and the connector allows for validation, which also worked. 
Great! 
Not really. 
The next day, the problem started again. And this time the connector validation was also failing. 
After some more digging around,  someone figured out a brute force way of updating the SPF record with +ip6:2603:1000::/24  which sort of blanket whitelists the Microsoft IPV6 range. 

The connector validated successfully after this. And outgoing mails to Gmail started working again!

Now we wait and see what Gmail does next :)