You don't usually even need to restart your named in order for the change to take effect, but without more information about what platform you are on and who managed to configure your DNS for you in the first place, we can't really guess where you have it.

As such, no SPF records in the world are going to help you from Microsoft blocking you. Primarily, SPF is a mechanism for preventing others from sending forged email in your domain's name. If that's a problem you are currently experiencing then definitely, deploy SPF, with a nice and tight policy like you have. (Do you understand the difference between -all and ~all? By all means use -all if you can.)