I am trying to work with the lookup budget and dealing with a web host that also sends out email on behalf of the domain for various services who does not keep a tidy SPF itself. I have not ever run into this problem and my googlefu is failing me. I found an article and they termed it amending the records to include additional TXT records with further includes so that they are processed differently. I came up with the following:
"v=spf1 include:spf1.example.com include:spf2.example.com ~all"
"v=spf1 include:webhost.com include:morewebhost.com ~all"
"v=spf1 include:spf.messagelabs.com ~all"
This results in failure to see the additional spf1 and spf2 records (edit- to clarify, it does see the reference to spf1 and spf2 but that it doesn't see valid configs in either). Is this method a lost cause?
We recently garnered a contract with the example.com domain owners and migrated email from gmail to 365. I believe there was not a permerror until the introduction of messagelabs in the original line but despite removal of the gmail and 365 includes, it fails with just the web host and messagelabs includes.