Firts of all, free stuff is not accurate. Because a lot of users are paying for the 365 Office and business email. So your point is not at valid. I personally can tell you that none of my clients use Office 365 because of this reason since here in Mexico, at least 1 of every 10 emails wont arrive not even in the SPAM folder (including Goverment emails too). I urge them to use Gmail for Business instead.
If youre in Russia, the problem gets even worst, since they by default send to spam Yandex email and Yandex domain email. (the most used email over there).
Second of all, if it was so easy as changing the SPF record, we wouldnt have this conversation. The reallity is that you have to ask via email to Microsoft team for a manual removal of blacklist. And you can get blacklisted for something as simple as sending "too much email" via forms in your website.
My only suggestion to anyone using Hotmail is to change ASAP if you want a reall business email, since you wont get not even to SPAM emails from your clients. And that, I can guarantee as for now.