OK, this is back intermittently. It only happens at work, so may be a firewall issue (though the error message leads me to believe the connection was established but failed to authenticate, it does take about as long as a failed TCP connection attempt so maybe that's what's really going on).
I see one A record for smtp.cesmail.net from dig. Is that a round-robin?
It would be helpful to have a list of all the IPs used for that name so we can enable them all in our outbound firewall rules.