When running Outlook it displays the error message “We are unable to connect right now. Please check your network and try again later” and does not connect to Exchange Online.

Running the PowerShell command “Get-NetConnectionProfile” returns the following Ipv4Connectivity value:

Name             : ethernet1
InterfaceAlias   : Ethernet
InterfaceIndex   : 10
NetworkCategory  : DomainAuthenticated
IPv4Connectivity : LocalNetwork
IPv6Connectivity : NoTraffic

Issue was due to a problem with the Network Location Awareness (NLA) service being unable to access the URL http://www.msftncsi.com/ncsi.txt or (changed in later Windows 10 builds) http://www.msftconnecttest.com/connecttest.txt

After fixing the connectivity issue (proxy certificate issue) the command then updates the connectivity to:

Name             : ethernet1
InterfaceAlias   : Ethernet
InterfaceIndex   : 10
NetworkCategory  : DomainAuthenticated
IPv4Connectivity : Internet
IPv6Connectivity : NoTraffic

Then when Outlook is run it connects to the Exchange server as expected.

If the client can already access the test URLs then it may be due to network adapter settings.

Running the PowerShell command:

Disable-NetAdapterChecksumOffload -Name "*" -TcpIPv4

Disables the checksum offloading to the network adapter. It applies instantly.

Then running the PowerShell command “Get-NetConnectionProfile” lists the connection connectivity:

IPv4Connectivity : Internet

Then when Outlook is started it connects to the Exchange server as expected.
 

Thanks to https://purepcs.co.uk/kb/microsoft-connection-test-ncsi-and-office-365/ for the Checksum Offload command.