Truthly, I’m not sure what the cause of the issue is - I only suspect it to be a server configuration issue.
Using an external service to handle emails has always been the default way for me too. As I mentioned before, I use Mandrill (Paid SMTP service) linked to Ebizmarts Mandrill module to connect it all up.
I’ve seen a couple of people mention that they’ve had success using Gmail (SMTP service). Ref: Magento 2 Version 2.3 Using G Suite to Email Via SMTP M2 by Mageplaza
I realise this turns into a “workaround” for your issues rather than a “fix” to the original problem. But I’m not sure what else to suggest as I’m unable to recreate the issue.