Disabling Cached Exchange Mode on the Outlook Profile would fix the issue but we needed Cached Exchange mode to be enabled!
The protocol we were using is MAPI over HTTPs.
Outlook 2010 and 2013 connected fine with MAPI over HTTPs, only Outlook 2016 had this issue.
The issue turned out that the customer had disabled oAUTH on the MAPI over HTTPS virtual directory.
Below is the authentication settings setup on the customers Exchange 2016 server: