The instructions aren't completely clear about how to do this, so here is a little more info.
If you're using Office 365 you should already have a SPF .txt record on your domain that looks like this:
v=spf1 include:spf.protection.outlook.com -all
Because a domain can only have one SPF record, you will need to add the 'include:mktomail.com' text to the existing record. Just paste it in after the existing 'include' statement and a space, like so:
v=spf1 include:spf.protection.outlook.com include:mktomail.com -all
And you should be all set! It was a little tricky to figure out that there can only be one entry for the domain. Hope this helps somebody!
did that definitely work - is it verified with Marketo Admin > Email?
Yes, it is showing up as verified in the admin panel.