Then the send mail fails returning "Authentication error". Then the SMTP session times out.

Find out from your Exchange Server admin if they've enabled a feature that is very common in a lot of MTAs where you need to log in (authenticate) in order to relay mail through the server. That's what the statement above would imply.

My own personal email relays will not allow non-authenticated users to relay to remote domains without authenticating.