|My first guess was also that the problem is in our firewall, but I only asked our admin about a port being blocked. I will have to ask again about a possible black/white listing. Thanks for that suggestion.
As for the SMTP server, per MickeySoft's instructions I use smtp.office365.com and port 587 or 25. I suppose that address has its own autodiscover protocol. nslookup gives me the specific smtp server name outlook-emeaeast3.office365.com and 9 different IP addresses.
What I have been wondering about is, how MS Outlook contacts exchange online. Why is it not having any problem connecting?
My advice is free, and you may get what you paid for.