If you have come across this lovely message then you are at the right place. This was thrown up from Outlook with an Office 365 account. The following symptoms were present:
-You will need the internet for this
-Outlook kept reporting "Trying to connect".
-Microsoft Edge wasn't able to browse to any websites at all. Chrome and any other browser was fine.
You can check Outlook by Ctrl+Alt+right clicking Outlook's tray icon and selecting the test account option. Punch in you email and password - you'll get the above pop up error.
Here is a list of things you can try, in no particular order (although #1 sorted it for me in my case):
1. Create if not present or change of there the following regkey:
Set to 20 hex (DWORD) - implies favour IPV4 over 6.
(00 can also be tried) - IPV6 disabled.
2. Clear all MS related credentials from the credential manager (search inside the classic control panel)
3. Access the following registry path
Add a new entry of type REG_DWORD with the name EnableADAL with value 0
Remove the DisableADALatopWAMOverride entry if it exists.
4. Shut down all Office Apps
In Explorer, navigate to C:\Users\%Username%\AppData\Local\Packages\
Delete the Keys in the folder
Relaunch Outlook - Keys are re-created automatically.
5. Add the AAD broker plugins to the loopback exemption manager (yeah I know..)
For fun you can reference this MS article as well:
Reboot after making registry changes. I had to create a new Outlook profile as well.