Office365 SPF PermError: Too many DNS lookups

Apart from everything that has already been said, let's focus on this:

My question is the following: How do I work around this error? I know I can replace some  
records with their ip4 equivalent, but when doing this, the online troubleshooter of  
Office365 kept complaining that the record was not found:

I recently ran into the same problem.
While it is documented that it should work (http://community.office365.com/en-us/w/exchange/customize-an-spf-record-to-validate-outbound-email-sent-from-your-domain.aspx) we could never get it to verify with a different record.
It didn't matter if it was a:some.host.com or ip4:127.0.0.1, it always complained about the SPF record being wrong/missing.
In the end we changed the record to v=spf1 include:spf.protection.outlook.com -all to make the verification wizard happy and adjusted it back afterwards to the real record.

Answer taken from SO here Author: Swift. Adapted to fit the question. Also, have a read here on general SPF stuff.

We started with:

v=spf1 a mx include:_spf.google.com include:servers.mcsv.net include:sendgrid.net ~all

We get 10 total lookups before we throw the Too many DNS lookups error:

  2 (Initial TXT & SPF Lookups)
  2 (a & mx Lookups)
  1 (_spf.google.com)
  1 (servers.mcsv.net)
 +1 (sendgrid.net)
 -----------------
  7 Lookups

So without even following the included SPF records, we have 7 lookups.

Now, let's dive a level deeper.

1. _spf.google.com

The google SPF record evaluates to:

v=spf1 include:_netblocks.google.com include:_netblocks6.google.com ?all

Each of which resolve to the following values:

# _netblocks.google.com
v=spf1 ip4:216.239.32.0/19 ip4:64.233.160.0/19 ip4:66.249.80.0/20 ip4:72.14.192.0/18 ip4:209.85.128.0/17 ip4:66.102.0.0/20 ip4:74.125.0.0/16 ip4:64.18.0.0/20 ip4:207.126.144.0/20 ip4:173.194.0.0/16 ?all

# _netblocks6.google.com
v=spf1 ip6:2607:f8b0:4000::/36 ip6:2a00:1450:4000::/36 ?all

So google gives us 2 more lookups, bringing the total up to 9 Lookups.

2. servers.mcsv.net

Mailchimp is a bit of a doosey because it adds a whole 3 extra lookups:

v=spf1 include:spf1.mcsv.net include:spf2.mcsv.net include:spf.mandrillapp.com ?all

I would imagine that depending on what you're sending through Mailchimp, you might be able to remove one or two of these records (but you'll have to evaluated that yourself).

Anyway, those resolve to the following:

# spf1.mcsv.net
v=spf1 ip4:207.97.237.194/31 ip4:207.97.238.88/29 ip4:207.97.240.168/29 ip4:69.20.10.80/29 ip4:69.20.41.72/27 ip4:74.205.22.1/27 ip4:69.20.90.0/26 ?all

# spf2.mcsv.net
v=spf1 ip4:204.232.163.0/24 ip4:72.26.195.64/27 ip4:74.63.47.96/27 ip4:173.231.138.192/27 ip4:173.231.139.0/24 ip4:173.231.176.0/20 ip4:205.201.128.0/24 ?all

# spf.mandrillapp.com
v=spf1 ip4:205.201.136.0/24 ip4:205.201.137.0/24 ?all

This brings us up to a total of 12 Lookups (Which is two over the limit already).

2. sendgrid.net

SendGrid ends up being the fewest number of additional lookups for us.

v=spf1 ip4:208.115.214.0/24 ip4:74.63.202.0/24 ip4:75.126.200.128/27 ip4:75.126.253.0/24 ip4:67.228.50.32/27 ip4:174.36.80.208/28 ip4:174.36.92.96/27 ip4:69.162.98.0/24 ip4:74.63.194.0/24 ip4:74.63.234.0/24 ip4:74.63.235.0/24 include:sendgrid.biz ~all

So the only additional lookup here is sendgrid.biz, which evaluates to:

v=spf1 ip4:208.115.235.0/24 ip4:74.63.231.0/24 ip4:74.63.247.0/24 ip4:74.63.236.0/24 ip4:208.115.239.0/24 ip4:173.193.132.0/24 ip4:173.193.133.0/24 ip4:208.117.48.0/20 ip4:50.31.32.0/19 ip4:198.37.144.0/20 ~all

This brings our grand total up to 14 lookups.

So our grand total is 14 Lookups. We need to get that down to 10. I've outlined a couple of options below, you may need to use more than 1 of them to get it down.

1. Directly include some of the redirected spf records. Now that we know which servers the spf records redirect to, you could cut out the middleman and include them directly. Note: If any of the services end up changing their SPF records, you'll have to go through the process of updating yours manually.

2. Remove some of the services that you're using. Not sure what your use case is for having all of these services, but there's definitely some overlap that you might be able to use. For instance, SendGrid supports (1) transactional outgoing mail, (2) newsletter / marketing emails, and (3) incoming mail. So there may be some reducible redundancy.

3. Remove the MX record if it is redundant. Depending on your setup, the MX lookup can be redundant.

You can just use an SPF Proxy service like spfproxy.org. Then you don't need to flatten DNS entries into IP addresses or even screw around with subdomains. You just setup SPF Proxy and it will do all the lookups on the backend. It's the only way I've found to solve this problem elegantly.