Could you please provide more information,
What is the version of your exchange server?
Are you using M365 pro plus C2R?
Have you deployed Exchange Hybrid?
Any changes to the DNS?
Is it happening for all users or some?
Can you do outlook Test Email AutoConfiguration and check if O365 autodiscover is the first URL its trying?
Hold Ctrl+right click on the outlook icon in system tray and click on "Test Email AutoConfiguration" and uncheck "use Guessmart" and "Secure Guessmart Authentication" and click on Test. Review the results in log tab
What's the detailed version of your Outlook? You can check from File > Office Account > About Outlook.
For Outlook 2016 version 16.0.6741.2017 and later versions, Outlook will attempt to retrieve Autodiscover from O365 as priority.
You can exclude the autodiscover queries to Office365 using the registry on the affected machine and check its connecting locally using SCP while joined internally
Create a DWORD value for ExcludeExplicitO365Endpoint and change the value to "1":
If the above suggestion helps, please click on "Accept Answer" and Upvote it.
Glad to know it worked and was helpful :)