RArtes

I would recommend changing your MX record to point to Office365, and keep Exchange on-premise for local outgoing SMTP only. Microsoft is a big corporation and their management of your mail is always going to be better. Especially for education, you get great value for money with Office365, security and filtering are inbuilt. Take the strain off your in-house mail servers and offload to Microsoft. Managing e-mail has become much easier since we migrated to Office365. And best of all, if something goes wrong, 90% of the time we can blame Microsoft.

Reverse DNS was the issue for me. As soon as we added the entries to the Reverse Lookup Zone in DNS, then it started working.