I ran into this with another ISV product and it looks like Microsoft introduced some "speedbumps" for those that have not disabled TLS 1.0 and 1.1.   They occur randomly which is why sometimes it works and sometimes it doesn't.  More info here: 

https://techcommunity.microsoft.com/t5/exchange-team-blog/new-opt-in-endpoint-available-for-smtp-auth-clients-still/ba-p/2659652

Thank you for this information.

Thank you so much for posting this!  My IT guy was able to fix the problem once I relayed this information to him.

You're welcome!  I am happy it helped.