Outlook prompts for credentials with Exchange 2010 and 2013/2016 coexistence

For some time ago I stumbled upon a strange credential prompt in Outlook for an entire organization after changing the Autodiscover namespace to point to the Exchange 2016 servers.
Outlook 2010 Credential Prompt

When you search for this issue with your favorite search engine you get several hits where other administrators and users got the same error.  The solutions posted in the forums, blogs and articles were all different but they were all touching the same subject, Autodiscover.
So I decided to try the top solutions i found to see if it resolves my issue.

Our servers:
1 Exchange 2010 CAS/HUB
1 Exchange 2010 Mailbox
2 Exchange 2016 Mailbox (Mailbox role in Exchange 2016 has all Exchange roles except Edge)
Namespace URLs for both Exchange 2010 and Exchange 2016:
Outlook Anywhere: mail.contoso.com
OWA: https://mail.contoso.com/owa
ECP: https://mail.contoso.com/ecp
ActiveSync: https://mail.contoso.com/MicrosoftServerActiveSync
EWS: https://mail.contoso.com/EWS/Exchange.asmx
OAB: https://mail.contoso.com/oab
MAPI: https://mail.contoso.com/mapi
Autodiscover SCP: https://mail.contoso.com/Autodiscover/Autodiscover.xml
We are using a SRV-record for autodiscover instead of a A-record for the external DNS Zone.