A little like the Y2K bug, it’s been found that Microsoft have a bug in their malware filtering service that is part of Exchange 2016 and later that only started at midnight on Jan 1st 2022. The effect of this bug is that mail delivery stops entirely IF the Malware scanning filter is being used (which by default it is).
Here’s a sample of some of the messages you would have seen
Microsoft announce the issue on their blog here stating that it will take several days at least to provide a real patch for it.
In the meantime however you can use the following few lines to quickly disable the Malware Filtering server on your Exchange servers
Get-MalwareFilteringServer | Set-MalwareFilteringServer -BypassFiltering $true
Please note that when you do this, you will bypass any filtering that was taking place, therefore real malware might slip through. Fingers crossed that Microsoft can get this patch sorted sooner than later!