Thanks for the response KevinShaughnessy.
For KSchneider42 (or anyone else that may be following along):
I finally got my support ticket escalated and, while I never really got an explanation of why the issue started so suddenly after years of running smoothly, I was directed to this support page:
https://learn.microsoft.com/en-us/exchange/troubleshoot/mailflow/email-stuck-queues
After modifying MaxPerDomainOutboundConnections and MessageRetryInterval to the suggested values, my connection issues instantly disappeared and have yet to return (knock on wood). Note that I did not modify the SmtpConnectorQueueMessageCountThresholdForConcurrentConnections setting in the Edgetransport.exe.config file.