Last weekend I transitioned a company website and corporate tools from an old server to a VPS which was set up beforehand on test.example.com and then moved to example.net. While the box does send some automated messages it is not our mail exchange server. The mail exchange server in DNS is still set to our custom microsoftonline url, this URL didn't change.
Going through the error logs I see that some emails, to legitimate users, are being rejected by the VPS. 99% of the emails sent go through microsoftonline's services and are delivered to the recipient. In fact one email from a colleague in China was delivered correctly through Microsoft and the next email from the same person was rejected by the web-server.
My problem is not that the server rejects emails - I don't want to relay external emails, my problem is that it catches these emails at all.
Any Input is appreciated! I am no exim, dns, or webhost master.