It has been a common situation, when using OVH IP’s, that Microsoft blocks all mails sent to their domains (outlook, live, hotmail, etc) or immediately places them on their Junk mail folder.
“Deliverability to Outlook is based on your reputation. The Outlook Smart Network Data Services (SNDS) gives you the data you need to understand and improve your reputation at Outlook. But just looking at the data isn’t enough! Maintaining a good reputation is a lot of work.” (Microsoft)
In order to bypass this situation, you need to configure rDNS, SPF, MX, DKIM, close any open relays you might have on the server.
You can use mxtoolbox.com to check for vulnerabilities regarding your mail (bkacklisted, wrong rDNS, SPF, MX , DKIM configuration).
If your domain provider is Godaddy, and you use their nameservers, you might get an SOA error, as it is not compliant with RFC 1912. Despite that, that won’t be an issue for delivering mails to Microsoft domains.
After all is correctly setup, you can request your IP to be cleared. That can be done here: https://postmaster.live.com/snds/addnetwork.aspx
You can also register for free for JMRP program, and get reports of your mail traffic to their servers. It is quite useful if you host multiple mail server domains, whereas you can check what the problems are with your mail clients and proceed with corrective measures.
