Exchange Online Hybrid - Autodiscover works for Outlook 2016 clients, but fails for Outlook 2013

We have a hybrid Exchange environment with Exchange 2010 and a small number of mailboxes migrated to Exchange Online. We are using ADFS for authentication.

However, for mailboxes that have been migrated to Exchange Online, the Outlook 2013 autodiscover process fails.

Oddly, Outlook 2016 autodiscover works fine. Autodiscover also works fine for on-premise mailboxes. Users can authenticate to Outlook web fine via ADFS.

Outlook 2013 seems to have a problem at the point it is redirected to https://autodiscover-s.outlook.com/autodiscover/autodiscover.xml (normally the final step after first contacting on-premise CAS server). It then shows a logon prompt, however no credentials are accepted. If credentials are provided, they fail with 0x80004005. Screenshot below.

Troubleshooting attempted:

• Verified that autodiscover-s.outlook.com is in Local Intranet zone and WIA is enabled.
• Verified that traffic is not passing through proxy.
• Enabled Modern Authentication for Outlook 2013
• Found this KB article (https://support.microsoft.com/en-gb/help/2785498/outlook-autodiscover-fails-with-error-0x80004005-outlook-2013-or-0x800) - not relevant because no boot registry key exists.