When on-boarding a domain to Exchange Online there is support documentation available detailing the DNS entries required for the domain to be successfully validated. One item not explicitly stated in the documentation with the SPF record is that the required include must be in the TXT record directly on the domain record.
It won’t be seen by the Microsoft 365 validation process if include:spf.protection.outlook.com element is added to an SPF redirect record or another include as shown by the example below.
Example that won’t be validated by Microsoft 365
Let’s assume this is my base SPF record for the domain itdevlab.au
v=spf1 include:spf.mail.itedevlab.au -all
The TXT record on the domain spf.mail.itdevlab.au could then be the following, however it would fail the Microsoft 365 validation as the entry for spf.protection.outlook.com is not in the SPF record at the domain level.
v=spf1 include:spf.protection.outlook.com include: spf.mycloudservice.com -all
Temporary step to allow validation
Using the below as the domain SPF record would be considered in-efficient as the spf.protection.outlook.com entry is effectively included twice, however it will get you past the Microsoft validation stage.
v=spf1 include:spf.mail.itedevlab.au include:spf.protection.outlook.com -all
Once the validation has been completed the original SPF record can be retained.