I am having the same issue and it started on 2/22/18. Oryx, i am on the same boat as you. O365, no open relay, no blacklist, dkim and spf configured correctly. Users are getting irritated. What is going on? I cannot contact Messagelabs since we are not a coustomer. Can't call the IT dept of each company blocking us. They are huge businesses and don't have their internal IT staff easily available to troubleshoot.