Long Time to Send Mail to MS owned services from Exchange 2019

Question

Hi All, first post here. I have mediocre to OK Exchange skills, so please, be gentle.

This is a standalone Exchange on prem with sufficient hardware resource. Backpressure on all counts shows "low". WAN is 100 Mbps (fiber)

My Exchange keeps in the queue all messages sent only to MS owned domains (outlook.com, hotmail, live), and to other domains if they are using Office365. Messages are kept in the transport queue for anywhere between and hour and 12 hours. Attachments appear to make it worse. Receiving is a bit on a slow side, but acceptable.

The problem started on Monday last week. No changes were done to the server or the network, except for the Y2K22 issue, that I resolved temporarily on Jan. 1. by disabling anti-malware scanning.

There are no issues sending email to any other domains - messages are pushed right away, and they are received on the other end equally fast.

The messages that fail to leave the queue as expected are flagged with the following:

• Last Error: 451 4.7.0 Timeout waiting for client input
• Last Error: 421 4.4.2 Connection dropped due to ConnectionAborted
• Last Error: 450 4.4.318 Connection was closed abruptly (SuspiciousRemoteServerError)
• Last Error: 451.4.4.397 Error communicating with target host

Sometimes, the same mail message may flag a different error code upon consecutive retries, so sending to xyz@harsh.com .com may come back with 421 4.4.2 or 450 4.4.318.

I have since applied the Y2K22 fix from Microsoft, as well as the latest CU for Exchange. That was last night

The messages flow a bit better, but there are still delays of about 30 to 60 minutes based on about a dozen tests. Transmissions error out flagging one of the above listed error codes, before eventually being delivered.

What throws me off is that this happens only when mail is sent to any domain owned by Microsoft. Absolutely no issues with any other domains.

Any thoughts?