On the first day of a new year (for me it was the second day) Microsoft gave us a present to work on that affects Exchange servers. Affected systems could not send or receive mails, messages would get stuck in message queue with the error "Message deferred by categorizer agent". Here are the two relevant event viewer entries:
The issue here is that the malware filter could not scan the message because of this error (it has to do with date time not fitting into 32 bit integers anymore) and the message would not get sent to the recipient. To temporarily resolve the issue, you can disable antimalware.
Open PowerShell as admin.
& "$env:ExchangeInstallPath\Scripts\Disable-AntimalwareScanning.ps1"
Restart MS Exchange Transport Service
Restart-Service MSExchangeTransport
References: