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

Notice: This post does not contain any pictures. They were all lost during the import from my old Gonjer.com site. I do apologize for that but I hope that the post will still help.

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.
Picture: 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/Microsoft–Server–ActiveSync
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.

• Public Folder authentication errors with Outlook Anywhere.
  Microsoft KB2834139
  This didn’t seem to solve my issue since we removed all Public Folders and related items before installing Exchange 2016.

• Enable Kernerl-Mode authentication for EWS and Autodiscover.
  Garzafx Blog
  This didn’t resolve my issue, but we noticed that a few users could use Outlook after entering the credentials. Not a satisfied solution since Exchange deliberately disable Kernel-Mode authentication and the majority of the users still got the prompt. However this solution pointed me in a direction that it isn’t necessary that the Autodiscover has wrong settings.

• Set CertPrincipalName for OutlookProvider settings.
  This command will only work is you use a wildcard certificate in Exchange.
  
  PowerShell

  Set-OutlookProvider -Identity EXCH -CertPrincipalName msstd:*.contoso.com

  1	Set-OutlookProvider -Identity EXCH -CertPrincipalName msstd:*.contoso.com

  
  I’ve received some information regarding changing the Outlook Providers from others that say the providers does not provide any functionality or fixes for Exchange 2013 or 2016. Didn’t solve my problem.

• Change the default Application Pool run account to ‘Network Service’.
  Microsoft KB2990117
  This knowledge base seams to be our exact problem but both the workaround nor the hotfix didn’t resolve my problem. Note: This hotfix is the first fix that Microsoft support recommended me to do.

• Authentication protocols and Windows Authentication providers.
  Microsoft support recommended me to verify the authentication protocols for Autodiscover and EWS. The first this I checked was the on Exchange 2010 CAS IIS and more specifically the Windows Authentication Providers. I noticed that the NTLM was the on the top and Negotiate at the bottom.
  Picture: Exchange 2010 IIS Settings.
  
  
  The same settings for EWS. Then I checked the Exchange 2016 IIS and the Windows Authentication Providers and noticed that Negotiate was on top.
  Picture: Exchange 2016 IIS Settings.I then moved NTLM to the top and ran ‘iisreset /noforce’. I immediately tried Outlook and discovered that it worked, not credential prompt!
  However after 15-20 minutes the credential prompt was back even though I was successfully in Outlook. I went back to Exchange 2016 to verify the providers and noticed that Negotiate was on top again. After numerous tries, restarts web.config settings the Negotiate was still on top. I asked Microsoft Support why, and they responded that this is my design, couldn’t get a more detailed answer from that person. Does anyone know why Negotiate is supposed to be on top?
  This didn’t solve my problem but it pushed me in the right direction, the authentication problems are messing with me.

• Move Arbitration mailboxes and verify OAB.
  I know this is really bad. Move the arbitration mailboxes is one of the first things you do when setting up coexistence Exchange. I’ve missed to move 2 out of 4 SystemMailboxes.
  This is the thing that Microsoft Support helped me to discover. So I went for it and started to move the Arbitration mailboxes to Exchange 2016 from Exchange 2010:
  
  PowerShell

  Get-Mailbox -Arbitration | New-MoveRequest -TargetDatabase 'MDB01'

  1	Get-Mailbox -Arbitration | New-MoveRequest -TargetDatabase 'MDB01'

  
  When the Arbitration mailboxes were moving to Exchange 2016 I wanted to check what OAB was assigned to all Databases. I noticed that on Exchange 2010 databases the “Default Offline Addressbook” was used and on the Exchange 2016 databases the “Default Offline Addressbook (2013)” was used. I knew that this would cause some troubles for Arbitration mailboxes and when I start to migrate users to Exchange 2016.
  I ran the following command to assign the correct OAB for all databases:
  
  PowerShell

  Get-MailboxDatabase -Server Exchange2010 | Set-MailboxDatabase -OfflineAddressBook 'Default Offline Address Book (2013)'

  1	Get-MailboxDatabase -Server Exchange2010 | Set-MailboxDatabase -OfflineAddressBook 'Default Offline Address Book (2013)'

  
  When the System Mailboxes were migrated to Exchange 2016 and all Mailbox Databases in the organization used the same OAB i went to verify the Authentication Providers for OAB in IIS. I noticed that NTLM was the top used provider for both Exchange 2010 och Exchange 2016 witch was a little odd since Autodiscover and EWS used a forced Negotiate provider. This got me started thinking that this may be a client related issue.

  I logged in on my test client with Outlook 2013 and still got prompted for credentials. I entered my credentials and everything started to work!

Conclusion:
Verify that you have moved all Arbitration Mailboxes to the new Exchange servers.
Verify the Windows Authentication Providers settings.
Verify that the correct OAB is used for every Mailbox Database.
Verify Outlook Anywhere is configured correctly:

For my environment this is the output that works best for me:

SSLOffloading                      : False
ExternalHostname                   : mail.contoso.com
InternalHostname                   : mail.contoso.com
ExternalClientAuthenticationMethod : Ntlm
InternalClientAuthenticationMethod : Ntlm
IISAuthenticationMethods           : {Basic, Ntlm, Negotiate}

I hope this helps anyone else that have problems with credential prompts in Outlook.