Autodiscovery issue

Hi

In the last week, my client, who has been on Office 365 for 3+ years, has been having issues with adding an Office 365 account to outlook 2016. Either Office tries to add the account as an IMAP account and then complains about an invalid certificate or it just plain fails with "an error has occurred".

This client has their DNS settings with Cloudflare, which has never been an issue before and when I ping the autodiscovery url, it correctly redirects me to autodiscover-au.outlook.com.

I have spoken to a technical (not Microsoft as this licence is sold by a reseller) who insists it is an application installation issue and the correct registry entries have not been created and that I need to add an autodiscovery record in the registry. The problem I have with this advice is that the error occurs on multiple machine and even on my own PC with Office 2010 and another with 2016 installed. I am not in the office when I tested it on my personal PC, just to ensure it's not an office/domain issue.

Also, I have many client using Office 365 and have successfully added some of their emails on these computers so not really sold on the registry fix as the solution. The fix will work but that is an extreme measure and something that I would have to apply to all computers and I would prefer to understand and fix the core issue.

In the Admin console of Office 365, it complains about the DNS records not being correct but that is due to Cloudflare blocking them from prying eyes. If I ping the records (as mentioned above), I get the desired results.

Can anyone point me in the right direction of how to solve this mystery

Thanks