Office 365 & Outlook Configuration issues

One of my clients using Office 365 (E3), direct with Microsoft, not through a 3rd party such as GoDaddy.

Now, this morning CEO's PA reports that when she opens his Inbox and Calendar in Outlook (2016, Cached Exchange Mode and she has Full Mailbox Access) both show as empty which she (and I) know is wrong.

So I logged onto http://portal.office.com as the CEO and eveyrthing is as expected, data in both Inbox & Calendar.

I log onto his desktop session (Citrix XenApp 6.5) and open Outlook and I get the following pop up:
---------------------------
Microsoft Outlook
---------------------------
Outlook cannot log on. Verify you are connected to the network and are using the proper server and mailbox name.  The Microsoft Exchange information service in your profile is missing required information. Modify your profile to ensure that you are using the correct Microsoft Exchange information service.
---------------------------
OK  
---------------------------

So I fire up the Mail Control Panel and cannot get into the Server Properties of his existing Mail Profile (which I know was working last week as I had to troubleshoot an issue for him). So I go to create a new one. I use the automated connection and it pops up with this:
It has picked up his Primary SMTP address which is also his Office 365 username without fail but that is not the server name I expected. Checking online and that server name is part of GoDaddy's Office 365 infrastructure,

My client is not using GoDaddy for Office 365, just to host their corporate website. Last week, the client moved the hosting of their corporate website over to GoDaddy from KCOM. I change the DNS A Records for the www records to GoDaddy and new website is up and running without issue.

So I suspect that something is happening with DNS and redirecting to GoDaddy for Office 365.

I have logged into the Office 365 Admin page and navigated to the Domains section, opened up the domain that they are using and ran the 'Check DNS' test:
(excuse the zoom level). We can ignore the TXT error as the client has a custom SPF record that allows their Helpdesk system to send emails out.

any idea why, when trying to configure Outlook 2016 the client is being pointed at GoDaddy?

Office 365 Service Health has no reported Incidents that may be causing this.

Thanks
Mark