When did it begin and how often does it occur?
This happens everytime. - When we install a new image via SCCM or even a straight from the CD/ISO installation with no other applications other than installing MS Office 2013 Pro Plus (with SP1) you run Outlook for the first time and get the first time run wizard. The autodiscover pulls in your name and email address. The next screen runs through the three checked tasks but fails on the last task with an error that it cannot find or see the Exchange server or that the Exchange maybe offline.
This is not correct as the exchange server is online and the client machine can ping, push and pull files through the UNC path etc.
This is run whilst the IE Settings > Connections > LAN Settings > Proxy is enabled. When this is DISABLED it works as it should do as you would expect the end client to work and can also send and receive emails. Obviously this is not the fix as the end client must retain the Proxy setting. (This is a third party proxy so nothing I can do to edit or monitor their servers)
We have added the exchange server to the exclusion list but Outlook is still persisting in "thinking" the Exchange server is offline/un-contactable.
The FQDN of the Exchange server is called SRV788.ABC.sub.net So the following has been attempted as exclusions to fix the issue but nothing has worked: (server names obviously sanitised to protect the client)
SRV788.ABC.sub.net
*.ABC.sub.net
*.sub.net
*.net
10.20.1.30 (Private IP of the EXCH)
10.20.1.*
10.20.*.*
10.*.*.*
* (I would expect this to have worked in its worst case scenario as this surely would exclude everything, but still fails.)
What's the environment and are there recent changes?
Same results on:
Windows 10 1809
Windows 10 1903
Windows 10 1909
Windows 10 2004
Windows 10 20H2
The Exchange Server was originally on 2010 and is now in Exchange 2016 but no traces of 2010 in ADSI edit
This is where things get really funky, this all works on an old SCCM build on Win 10 [1909] on the same switch and VLAN etc.So some jiggery pokery must have taken place years ago by the person who previously built tha last image. Un-contactable. Ive been looking through the registry and nothing stands out to me.
We have raised a call with MS premier support which hasnt not been answered yet and I am hoping to crack this by the weekend to meet a deadline.
Your 'hopefully'
Lee

Does the email address fit to your domain? so user@yourdomain.tld ?
The client uses autodiscover to find the server details. To prove that autodiscover works, you may check the ISS logs of exchange, it you see the request.
My imagination is, that something with your autodiscover doesn't work as expected.
You may alkso check on a working client, which is connected via Proxy, what you get if you CTRL-RightClick on the outlook tray icon, there you can select an option to check autodiscover.