Hi
I had a similar problem;
We host Plesk inside Microsoft Azure, by default Microsoft will black list its own IP inside Office365 and outlook.com.
https://blogs.msdn.microsoft.com/mast/2016/04/04/sending-e-mail-from-azure-compute-resource-to-external-domains/
We don't run any email...