With Microsoft you need to fill in a form first specifying your IP address and they will whitelist you, at least it used to work like that the last time I set up a new mail serer a few years ago.
The only time I've had to do something like that is when I moved my server to a Colo and the previous owner of that ip address had sent spam and so that ip address was marked as a spammer. I had to go to several places to mark the address clean since there are multiple blacklists.