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:

HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\Tcpip6\Parameters\DisabledComponents

Set to 20 hex (DWORD) - implies favour IPV4 over 6.

(00 can also be tried) - IPV6 disabled.

Reference

2. Clear all MS related credentials from the credential manager (search inside the classic control panel)

Reference

3. Access the following registry path

HKEY_CURRENT_USER\Software\Microsoft\Office\16.0\Common\Identity

Add a new entry of type REG_DWORD with the name EnableADAL with value 0

Remove the DisableADALatopWAMOverride entry if it exists.

Reference

Reference2

4.  Shut down all Office Apps

In Explorer, navigate to  C:\Users\%Username%\AppData\Local\Packages\

Microsoft.AAD.BrokerPlugin_cw5n1h2txyewy\AC\Microsoft\Crypto\TokenBindingKeys\Keys

Delete the Keys in the folder

Relaunch Outlook - Keys are re-created automatically.

Reference

5. Add the AAD broker plugins to the loopback exemption manager (yeah I know..)

Reference:

https://techcommunity.microsoft.com/t5/Outlook/Outlook-2016-error-0xCAA70004/td-p/136962

https://github.com/tiagonmas/Windows-Loopback-Exemption-Manager



For fun you can reference this MS article as well: 

https://docs.microsoft.com/en-us/office365/troubleshoot/administration/connection-issue-when-sign-in-office-2016

Reboot after making registry changes. I had to create a new Outlook profile as well.