microsoft office 365 - Office365 SPF PermError: Too many DNS lookups

We are migrating from a self hosted mailing platform to Office365 for Businesses. Everything went fine, except for the SPF record. At the moment, we have v=spf1 a mx include:spf.mtasv.net -all as TXT record, but Office365 has to allow v=spf1 include:spf.protection.outlook.com -all too. So, I went ahead and and merged them into: v=spf1 a mx include:spf.mtasv.net include:spf.protection.outlook.com -all. When checking this SPF record against the domain of studentkickoff.be, this results into a PermError SPF Permanent Error: Too many DNS lookups.

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:

Thanks in advance!

Answer

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.