Hi,
I understand it could be disappointing as the Autodiscover is not working as expected. I want to know whether this issue occurs to all Outlook 2013 and Outlook 2016 machines, if this occurs to all these versions machines, I suggest you post the question
in the Exchange Online forum to troubleshoot this issue:
https://social.technet.microsoft.com/Forums/msonline/en-US/home?forum=onlineservicesexchange
Also, have you tried the Remote Connectivity Analyzer? What's the result?
https://testconnectivity.microsoft.com/
Regards,
Melon Chen
TechNet Community Support
Please remember to mark the replies as answers if they help, and unmark the answers if they provide no help. If you have feedback for TechNet Support, contact
tnmff@microsoft.com.