Got a call from a client today that my email are block from outlook.com, live.com and hotmail.com. Tried to talk to tech support which did not help. In the end I found a link to add my server ip to their white list.
If anyone else is looking for this here you go: https://support.microsoft.com/en-us/getsupport?oaspworkflow=start_126.96.36.199&wfname=capsub&productkey=edfsmsbl3&locale=en-us&ccsid=635639051175184163
Hope this saves you some time.