"Just an update for anyone with a similar issue - with some fresh eyes and some more googling it sounds like this may be caused by some SMTP rate limitations built into the AWS EC2 network as Spam prevention.
They have a form to register to remove outgoing smtp connection limitations here:
I've submitted and will update if this resolves the issues I was seeing."
"Amazon SMTP traffic management indeed seems to have been the cause. Within a couple of hours of filling out the above form, I got an email confirmation from AWS that "traffic restrictions had been removed" and normal function resumed immediately.
Confusing the matters is that this SMTP traffic management is not documented well (and sometimes with contradicting information). It does not appear to be a hard cap limit, nor does it trigger any notification when it's applied - it actually appears to be a *throttle* on common SMTP ports, triggered by a very small number of connections, beyond which it allows a certain number of connections per/hour - which would absolutely create the kind of "intermittent" connectivity issues I saw (and the odd delivery order of mail in the queue depending on when a retry "won the lottery" to negotiate a connection).
Anyway - I hope that info is of some use to others in the future!"
Guide: Installing Telnet In CentOS/RHEL/Scientific Linux 6 & 7
Amazon Web Services' Reply to Teo En Ming
We approved your request for the removal of the EC2 email sending limitations on your Amazon Web Services account! If you requested removal of email sending limits on any other Amazon Elastic IPs, they've also been removed.
Singaporean Mr. Turritopsis Dohrnii Teo En Ming's Academic
Qualifications as at 14 Feb 2019 and refugee seeking attempts at the United Nations Refugee Agency Bangkok (21 Mar 2017), in Taiwan (5 Aug 2019) and Australia (25 Dec 2019 to 9 Jan 2020):