It occurred to me this morning that I've seen this before. I looked through my notes and the last time we had this issue was in July of 2014 and it resulted in us being blacklisted on Microsoft's email domains. Back then, the fix was to disable ESMTP inspection on our Cisco ASA.
I had a look at our ASA config this morning and lo and behold ESMTP Inspection was turned on again. We made some significant network changes over the summer that involved some pretty major ASA configuration changes and I'm guessing we omitted turning it off.
The nature of the failure was very random and infrequent back then which might explain why it took so long to manifest. However, it's never caused the server unresponsiveness issues I saw yesterday.
Anyway, I'll keep an eye on the logs and will update this thread when I know more.