Further update .. we still have this problem. Microsoft have been unable to solve this one after 34 emails from them, and countless hours on the phone with shared sessions.
Here is what Microsoft have done so far, but the problem persists.
1 Created a new Outlook profile.
2 Re-installed Office with Easy Fix Tool.
3 Cleared cached credentials.
4 Created a new Windows Profile.
5 Ran Autodiscover regkey fix.
6 Disable IPV6
7 Made sure Network is set to Work instead of Public.
8 Deleted OST file.
9 Disable MFA.
10 Ran SaRA, but it gave a certificate issue which might be related to your Network.
11 installed a 64bit version of Office.