Microsoft O365 Delisting
Microsoft uses blacklist to protect the clients from spoofing and phishing attacks. IP address of the mail server may have been tagged by as a potential threat by Microsoft O365 protection systems. When Microsoft O365 adds the IP address to the list, it prevents all further communication between the IP address and any of Microsoft products customers through their datacenters.
Delisting is an easy procedure that would help solving these issues.
Step 1 Open the website https://sender.office.com/
Please note, that delisting may take up to 30 minutes.
Additional information about Office365 delisting issues is available at Microsoft site