Issue solved by reconfiguring servers:
Our failed configuration was: Outlook 2013 running on Windows 11 not connecting to Exchange 2010 running on Windows 2008 R2 via proxy.
Cause of failure: Windows 11 disables TLS 1.0 and TLS 1.1 by default and Exchange 2010 running on Windows 2008 R2 uses TLS 1.0. Therefore, Outlook can't communicate with Exchange. In our case, this happened when the Windows 10 workstations were upgraded to Windows 11 and is only noticed on workstations connected outside of the subnet the server is connected to. That is all of the workstations connected to the same subnet as the server never had a problem after the Windows 11 upgrade, but all of the workstations outside of that subnet failed with proxy (Error Code 80000000).
NOTE: This is a safe work around:
Solution: Add TLS 1.2 to the servers. This works because Windows 11 supports TLS 1.2 by default at this time and Windows 2008 R2 can be made to support TLS 1.2. This is great solution because only the server needed to be touched and we did not have to touch the workstations. We followed this for guidance: https://jaapwesselius.com/2018/10/05/exchange-2010-and-tls-1-2/
Fortunately, in our case Windows and Exchange were already well patched so we only needed to add these registry keys and DWORD items on the server and reboot it.
Here are all of the registry keys and DWORD items we added:
<<< TLS 1.2 stuff >>>
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\SecurityProviders\SCHANNEL\Protocols]
Added Key: TLS 1.2
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\SecurityProviders\SCHANNEL\Protocols\TLS 1.2]
Added Key: Client
Added Key: Server
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\SecurityProviders\SCHANNEL\Protocols\TLS 1.2\Client]
Added DWORD: DisabledByDefault = 00000000 (0)
Added DWORD: Enabled = 00000001 (1)
[HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\SecurityProviders\SCHANNEL\Protocols\TLS 1.2\Server]
Added DWORD: DisabledByDefault = 00000000 (0)
Added DWORD: Enabled = 00000001 (1)
<<< TLS 1.2 for .NET Framework 3.5.1 stuff >>>
[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft.NETFramework]
Added Key: v2.0.50727
[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft.NETFramework\v2.0.50727]
Added DWORD: SystemDefaultTlsVersions = 00000001 (1)
[HKEY_LOCAL_MACHINE\SOFTWARE\Wow6432Node\Microsoft.NETFramework]
Added Key: v2.0.50727
[HKEY_LOCAL_MACHINE\SOFTWARE\Wow6432Node\Microsoft.NETFramework\v2.0.50727]
Added DWORD: SystemDefaultTlsVersions = 00000001 (1)