Category Archives: Exchange Hybrid

Exchange Hybrid

Exchange Resource Forest and Office 365 Part V

1 Comment

Upgrade to Exchange 2016

Two years ago I wrote a number of blogpost regarding an Exchange Resource Forest model and Office 365 starting at Exchange Resource Forest and Office 365 part I. There are four articles, all based on Exchange 2010 and at the end of each article you’ll find a link to the next article. In the more information section at the end of this blogpost you’ll find all links.

Over the years I have received numerous requests on how to continue; moving to Exchange 2016 in a Resource Forest or when all mailboxes are in Exchange Online, decommission the Resource Forest. This is not a problem, but brings a new challenge when it comes to the last Exchange server for management purposes that need to be kept. And yes, this blogpost is the preparation for the ‘decommision the resource forest’ blogpost 😉

I have a few customers running a resource forest environment, and all have this same problem. They must move away from Exchange 2010, either to Exchange 2016 or to Exchange Online (or both). In this blogpost I’ll discuss the upgrade from Exchange 2010 in a Resource Forest to Exchange 2016 (in the same Resource Forest of course) in a hybrid scenario. In one of the next blogs I’ll discuss the way to decommission the Resource Forest in a hybrid scenario.

Note. I did a webinar recently for Kemp on the Upgrading Exchange 2010 topic. It’s a Brighttalk hosted webinar that you can find here The Best Known Methods on Upgrading Microsoft Exchange.

Upgrading Exchange 2010 to Exchange 2016

Upgrading Exchange 2010 in a resource forest is not different then upgrading any other Exchange environment, not even when running this in a hybrid environment. These are the steps that need to be taken:

Design your Exchange 2016 environment (won’t cover that in this blogpost).

  1. Prepare Active Directory for Exchange 2016.
  2. Build your Exchange environment.
  3. Change client access to Exchange 2016.
  4. Run Hybrid Configuration Wizard.
  5. Move Resources to Exchange 2016.
  6. Decommission Exchange 2010.

Prepare Active Directory for Exchange 2016

Before you can install the first Exchange 2016 server, Active Directory needs to be prepared. This is only true for the resource forest, there’s no need to do this at the account forest.

You can prepare the Active Directory schema using the following command:

C:\> Setup.exe /PrepareSchema /IAcceptExchangeServerLicenseTerms

It is possible that the following error message is shown:

A hybrid deployment with Office 365 has been detected. Please ensure that you are running setup with the /TenantOrganizationConfig switch. To use the TenantOrganizationConfig switch you must first connect to your Exchange Online tenant via PowerShell and execute the following command: “Get-OrganizationConfig | Export-Clixml -Path MyTenantOrganizationConfig.XML”. Once the XML file has been generated, run setup with the TenantOrganizationConfig switch as follows “/TenantOrganizationConfig MyTenantOrganizationConfig.XML”.

This issue is covered in a previous blogpost: A hybrid deployment with Office 365 has been detected.

Build your Exchange environment

Exchange 2016 can be installed on Windows Server 2012 R2 and Windows Server 2016, I always recommend the latter because of support lifecycle. Windows Server 2019 and Windows Server Core are not supported for running Exchange 2016.

I prefer to install the Exchange 2016 server unattended, especially if you must install multiple servers. You can use a command similar to this:

C:\> Setup.exe /Mode:Install /Roles:Mailbox /DbFilePath:”F:\MDB02\MDB02.edb” /LogFolderPath:”F:\MDB02\LogFiles” /InstallWindowsComponents /IAcceptExchangeServerLicenseTerms

Unattended Setup

After installing the Exchange server, the server should be configured:

  • Virtual Directories; make sure you use the same internalURL and externalURL as the Exchange 2010 servers.
  • SSL Certificates.
  • Storage, Databases and Database Availability Group (when needed of course).
  • Relocate (IIS) logfiles.
  • Send and Receive Connectors (SMTP Relay).

Change client access to Exchange 2016.

When you have configured the Exchange 2016 it is time to test the proxy functionality from Exchange 2016 to Exchange 2010. The easiest way to test this is to edit the HOSTS file for the webmail.contoso.com and Autodiscover.contoso.com entries on a client and point it to the Exchange 2016 server.

hosts file

From the client, connect to the new Exchange 2016 server and start OWA with an Exchange 2010 mailbox. You should see the initial blue OWA screen:

Exchange 2016 OWA Login

And after logging on the yellowish Exchange 2010 OWA user interface. It will automatically proxy to the correct Exchange 2010 mailbox server:

Exchange 2010 OWA Login

The same should happen when you request the Exchange Web Services page on https://webmail.contoso.com/ews/exchange.asmx, this should also successfully proxy to Exchange 2010:

EWS proxy

One important thing here is that this is a down-level proxy only. This means that when a client does a request to Exchange 2016 for a resource on Exchange 2010 (down-level proxy, like in the previous example) it should work. If a client does a request to Exchange 2010 for a request on Exchange 2016 (i.e. up-level proxy) it fails. This is shown in the following figure, and it does not work.

downlevel uplevel

When all is configured and tested, DNS (internal and external) can be changed so that webmail.contoso.com and Autodiscover.contoso.com point to the new Exchange 2016 server. All clients will now connect to the new Exchange 2016 server and connect to their mailbox on Exchange 2010 without a problem.

One thing you must be aware of is RPC/TCP traffic (the original MAPI connection) between Outlook and Exchange 2010 if you are not running Outlook Anywhere. Outlook will still use RPC/TCP to connect to the CAS Array (this is the RPC Endpoint for Outlook) which is running on the Exchange 2010 servers. You can see that when checking the connection status in Outlook. In the following screenshot, outlook.exchangefun.nl is the CAS Array.

Outlook 2010 Connection Status

There are two entries shown, one is for the regular mailbox, the second is for accessing a shared mailbox on Exchange 2010.

When performing the Test E-mail AutoConfiguration check on Outlook 2010, you can see that RPC Connects to outlook.exchangefun.nl, but that OWA, EWS and OAB want to connect to webmail.exchangefun.nl, which is the Exchange 2016 server now.

Outlook 2010 Test Email AutoConfiguration

So, Outlook connects using RPC to the Exchange 2010 server and using HTTPS to connect to the Exchange 2016 server. From Exchange 2016 the connection is proxied to the correct Exchange 2010 server.

Note. Be aware that if you have configured Kerberos authentication in your Exchange 2010 environment you have to upgrade this to Exchange 2016 as well. This is documented in the Microsoft articles Recommendation: Enabling Kerberos Authentication for MAPI Clients, How to Enable Kerberos Authentication for Accessing Exchange in a Resource Forest andExchange 2013 and Exchange 2010 Coexistence with Kerberos Authentication. For Exchange 2010/2016 coexistence you can follow that last link.

Run the Hybrid Configuration Wizard

When all is running well it is time to upgrade the Hybrid Configuration by running the HCW on the Exchange 2016 server. You can find the latest version of the HCW on http://aka.ms/hybridwizard.

The HCW will detect the optimal Exchange server to configure (which should be automatically the Exchange 2016 server). You should select the Exchange 2016 server for the Receive Connector Configuration and the Send Connector Configuration. For the Organization FQDN I typically use the default FQDN (like webmail.contoso.com) to keep everything consistent. Sometimes I see admins use something like hybrid.contoso.com but that doesn’t bring much, except for more complexity.

HCW Organization FQDN

When reaching the end of the HCW you can select to upgrade the Hybrid Configuration. The original Hybrid Configuration was created on Exchange 2010, but now it is upgrade to Exchange 2016 so I don’t see any reason to not check the checkbox.

HCW Upgrade current configuration

The easiest way to check the new Hybrid Configuration is to see if free/busy works cross-premises. Open a mailbox in Exchange Online and check if you can plan a meeting with a mailbox in Exchange 2010 and check the availability of this mailbox. Baron’s mailbox is in Exchange Online, my mailbox is in Exchange 2010 (still). The free/busy request is sent to webmail.exchangefun.nl which is now the Exchange 2016 server. From there it is proxied to the Exchange 2010, and it works like a charm:

Cross-premises freebusy

To check if cross-premises mail security you can send an email from an online mailbox to an on-premises mailbox. If you check the headers, the SCL should have a value of -1 (which means it is treated as an internal message) and the X-MS-Exchange-CrossTenant-AuthAs should have a value ‘Internal’.

At this moment there is an Account and Resource Forest environment, where the Resource Forest contains an Exchange 2010/2016 coexistence environment. All clients, including Exchange Online connect to Exchange 2016 while recipients are still on Exchange 2010.

Exchange 2010 2016 Coexistence

Move Resources to Exchange 2016

At this moment, mailboxes can be migrated from Exchange 2010 to Exchange 2016. And to be honest, this is not that exciting. It is fully transparent for users. It is an online process, so the mailbox content is copied from Exchange 2010 to Exchange 2016 while the user continues to work. Only when the move is finalized, the user is presented the following message box and needs to restart Outlook.

The Microsoft Exchange Administrator has made a change

Now back to the RPC/TCP (MAPI) part earlier in this post. Exchange 2016 does not support RPC/TCP anymore, so when a mailbox is moved from Exchange 2010 to Exchange 2016, the protocol changes as well. In this case, it changes from RPC/TCP to Mapi/Http for Mailboxes, and to Outlook Anywhere for Public Folders (still on Exchange 2010, but Exchange 2010 does not support Mapi/Http).

Outlook 2010 Connection Status Exchange 2016

Public Folders (if any) must also be moved to Exchange 2016. This can only be done when all mailboxes are moved to Exchange 2016. A mailbox on Exchange 2016 can access Public Folders on Exchange 2010, but a mailbox on Exchange 2010 cannot access Public Folders on Exchange 2016. The Public Folder migration is covered in my previous blogpost Exchange 2010 Public Folder migration, which was also performed on my Exchange resource forest environment.

In an Exchange 2010/2016 coexistence environment there are two Offline Address Books:

  • Default Offline Address Book – used in Exchange 2010
  • Default Offline Address Book (Ex2013) – used in Exchange 2016 (the name was not changed when Exchange 2016 was introduced, not sure if this is a cosmetic bug but it does work correctly).

When configuring the Mailbox databases makes sure the \Default Offline Address Book (Ex2013) is set on the OfflineAddressBook property of the Mailbox database.

One pitfall that always takes more time than expected is the Receive Connector configuration, especially for SMTP relay purposes. Multiple devices (scanners, faxes), printers, applications, access on IP level, lack of documentation etc. Use the Protocol logging features on the various Receive Connectors to figure out what devices or applications are using these Connectors and configure them to use the Exchange 2016 server. But beware, this can take a lot of time ☹

Edge Transport Server

You might have noticed I have an Exchange 2010 Edge Transport server running. This is used for SMTP traffic to and from the Internet. My MX record is pointing to the Edge Transport server, but cross-premises SMTP is delivered directly on the Mailbox server.
When is the best time to upgrade the Edge Transport server to Exchange 2016? There’s no real rule of thumb for this. The Exchange 2010 Edge Transport server works fine with an Exchange 2016 Mailbox server, but the other way around also works fine. I typically upgrade the Edge Transport servers to Exchange 2016 after installing the Mailbox servers, but before moving Mailboxes. But there are much more options when doing this.

Decommissioning Exchange 2010

When all resources have been moved to Exchange 2016 you can decommission the Exchange 2010 environment. This is just a matter of:

  • Decommissioning Mailbox database copies.
  • Decommission the Database Availability Group.
  • Remove Mailbox databases.
  • Remove the Public Folder databases (if not removed earlier).
  • Change/Remove Send and Receive Connectors (also see previous section).

When all prerequisites for the decommissioning process have been met, the actual Exchange 2010 servers can be uninstalled. I still see admins just removing the Exchange VM’s but this is not a good idea since the Exchange configuration continue to exist in Active Directory.

Properly remove the Exchange 2010 server using Control Panel and Uninstall or change a program by deselecting all options as shown in the following screenshot.

Uninstall Exchange 2010

After a few minutes the Exchange 2010 server will be fully installed (the official way).

Summary

In this blogpost I explained how to upgrade Exchange 2010 to Exchange 2016 when running in a resource forest configuration, and in a hybrid configuration. The process is not very different from an upgrade in a ‘normal’ single forest, single domain environment, not even from a hybrid perspective.

The process is simple, upgrade Active Directory, install and configure the servers, change client access to Exchange 2016 and run the Hybrid Configuration Wizard. When done you can move resources to Exchange 2016 and when finished decommission the Exchange 2010 environment.

More information

 

Exchange Hybrid, Office365

HCW8001 – Unable to determine the tenant routing domain

3 Comments

As a consultant in messaging and collaboration I have created dozens of Exchange hybrid configurations that last years, ranging from Exchange 2010 to Exchange 2019.
Today we’ve run into an issue I have not seen before, the HCW8001 – Unable to determine the Tenant Routing Domain error:

Unable to determine the tenant routing domain

Note. In one of my earlier blogs Moving from Exchange 2010 to Office 365 somebody mentioned this specific error in the comments in September 2018.

When you click Learn more you are redirected to the following Microsoft page:
https://support.microsoft.com/en-us/help/3068010/unable-to-determine-the-routing-domain-for-the-cloud-organization-erro which states you have to enable Directory Synchronization using the following command:

Set-MsolDirSyncEnabled -EnableDirsync $true

Which of course we did, but no success.

Azure AD Connect was running fine, I checked the configuration (optional features) and found nothing strange and no errors were logged.

Optional Features

When checking the Microsoft Portal I could see Directory Synchronization was running:

Azure AD Connect

The tenant routing domain is typically something like <tenantname>.mail.onmicrosoft.com and this is set in Office 365 when installing Azure AD Connect. But when checking the Accepted Domains (in Exchange Online) this domain is not available:

Accepted Domains

There’s no way you can add this <tenantname>.mail.onmicrosoft.com domain manually (also not via the Microsoft Online Portal) so you are out of luck (I tried the Azure AD Connect server multiple times, but it didn’t work).

You can open a ticket with Microsoft Support or see if you can create a new tenant and start over again. Since this happens rarely I would be surprised you run into this again with a new tenant.

 

Exchange, Exchange Hybrid, Office365

Microsoft Teams and Exchange 2016

14 Comments

Microsoft Teams works best when your mailbox is in Exchange Online, and you have a license for SharePoint Online, and you have OneDrive for Business enabled.

When you have your mailbox in Exchange on-premises your options are limited, you have basic Teams functionality like audio/video and files, but that’s basically it. Not a trace of the calendar or the option to manage meetings in Teams. This is what ‘cloud partners’ have been telling me for a long time: “no, you must migrate your mailbox to Exchange Online” (and we can help you with that I was they were thinking…)

Teams with Exchange on-premises

But, if you have Exchange 2016 CU3 or higher things get better (I’m sorry if you are still running Exchange 2010). To enable the integration of Teams with on-premises Exchange 2016 you need to configure OAuth in your on-premises environment as outlined in my previous blog, and assuming you have Exchange hybrid configured of course.

When you have OAuth configured, Teams can access the on-premises mailbox on behalf of the user that’s logged on in Teams, making it possible to retrieve the user’s calendar. After configuring OAuth and without any additional configuration in Teams the user’s on-premises calendar (here in Exchange 2019) automagically appears:

Teams with Exchange on-premises OAuth

In the Teams client this is a view of your calendar, and using the new meeting option you can create new Teams meetings, invite people, set recurrence, select a channel etc. Invites are sent to other recipients using the regular Exchange process, and when accepted a response is sent (or not) back to your inbox. I never knew this was possible, but this is cool stuff.

Teams with Exchange on-premises new meeting

Integrating the calendar into Teams is a nice addition and it can help users with their daily productivity task. From a compliance perspective things are a bit different. Chats for example are not stored in the user’s mailbox, this is only possible for mailboxes in Exchange Online. The process responsible for copying Teams chat data from the Azure storage (outside of Office 365) simply cannot access the folder in the user’s mailbox.

But, for on-premises calendar integration in your Teams environment this is very nice.

More information

How Exchange and Microsoft Teams interact – https://docs.microsoft.com/en-us/microsoftteams/exchange-teams-interact

Configure OAuth authentication between Exchange and Exchange Online organizations – https://docs.microsoft.com/en-us/exchange/configure-oauth-authentication-between-exchange-and-exchange-online-organizations-exchange-2013-help

 

Azure AD, Exchange, Exchange Hybrid

Configure OAuth authentication in Exchange 2016

29 Comments

As long as I can remember the Hybrid Configuration Wizard finishes successfully, and itgenerates the error about the OAuth portion of the hybrid configuration.

Configure Intra-Organization Connector

HCW8064 – The HCW has completed, but was not able to perform the OAuth portion of your Hybrid configuration. If you need features that rely on OAuth, you can try running the HCW again or manually configure OAuth using these manual steps.

The Learn more option redirects to the Microsoft page Configure OAuth authentication between Exchange and Exchange Online organizations. I used that article for the PowerShell commands in this blogpost.

OAuth is used cross-premises to logon to other services, on behalf of the user. So, if you are logged on to some Microsoft service, this service can use OAuth to access services in Exchange on-premises and vice versa.

Example of these cross-premises services are:

  • Message Records Management (MRM).
  • Exchange in-place eDiscovery.
  • Exchange in-place Archiving.
  • Teams calendaring.

The HCW can configure Azure Active Directory for OAuth authentication, it can create the IntraOrganizationConnectors, but it cannot export and import the (self-signed) certificate on the Exchange server, nor can it (or does it) create the authorization server objects in Active Directory. So, time to test, guided by the Microsoft article and write down my experiences.

Note. This only works for Exchange 2013 and higher, I have been working on this in a mixed Exchange 2016 and Exchange 2019 environment.

Configuring OAuth between Office 365 and Exchange Online involve a number of steps.

Create Authorization server objects in Exchange on-premises

To create the authorization server objects in your on-premises environment enter the following commands in the Exchange Management Shell.

New-AuthServer -Name "WindowsAzureACS" -AuthMetadataUrl "https://accounts.accesscontrol.windows.net/contoso.com/metadata/json/1"
New-AuthServer -Name "evoSTS" -Type AzureAD -AuthMetadataUrl https://login.windows.net/contoso.com/federationmetadata/2007-06/federationmetadata.xml

Your verified domain contoso.com (in the command) should be something like exchangelabs.nl, and not <your tenant name> as outlined in the Microsoft article.

New-AuthServer

Enable the partner application for use with Exchange Online

The partner application was created in the previous step (the first command) and this should be enabled. Do this using the following command in Exchange Management Shell (on-premises):

Get-PartnerApplication | ?{$_.ApplicationIdentifier -eq "00000002-0000-0ff1-ce00-000000000000" -and $_.Realm -eq ""} | Set-PartnerApplication -Enabled $true

Export the Exchange authorization certificate

Authentication cross-premises is using certificates, so the on-premises certificate needs to be exported to Azure Active Directory. In case you were wondering where the CN=Microsoft Exchange Server Auth Certificate certificate was coming from when running the Get-ExchangeCertificate command in Exchange Management Shell, here you go.

Use the following PowerShell commands and store them in a PowerShell script called ExportAuthCert.ps1 or something and run it. This should export the OAuth certificate to a file called OAuthCert.cer.

$ThumbPrint = (Get-AuthConfig).CurrentCertificateThumbprint
If((Test-Path $ENV:SYSTEMDRIVE\OAuthConfig) -eq $false)
{
md $ENV:SYSTEMDRIVE\OAuthConfig
}
CD $ENV:SYSTEMDRIVE\OAuthConfig
$oAuthCert = (dir Cert:\LocalMachine\My) | ?{$_.ThumbPrint -Match $ThumbPrint}
$CertType = [System.Security.Cryptography.X509Certificates.X509ContentType]::Cert
$CertBytes = $oAuthCert.Export($CertType)
$CertFile = "$env:SYSTEMDRIVE\OAuthConfig\OAuthCert.cer"
[System.IO.File]::WriteAllBytes($CertFile, $CertBytes)

ExportAuthCert

Note. The Export-ExchangeCertificate command doesn’t work in this scenario since the self-signed certificate isn’t exportable.

Import the Exchange authorization certificate into Azure AD

The next step is to import the OAuthCert.cer certificate into Azure AD. Connect to the Microsoft Online service (Connect-MSOLService, if you don’t have this installed you can use the Install-Module MSOnline command) and run the following commands when connected:

$Cred = Get-Credential
Connect-MSOLService -Credential $Cred
$CertFile = "$ENV:SYSTEMDRIVE\OAuthConfig\OAuthCert.cer"
$objFSO = New-Object -ComObject Scripting.FileSystemObject
$CertFile = $objFSO.GetAbsolutePathName($CertFile)
$CER = New-Object System.Security.Cryptography.X509Certificates.X509Certificate
$CER.Import($CertFile)
$binCert = $cer.GetRawCertData()
$CredValue = [System.Convert]::ToBase64String($binCert)
$ServiceName = "00000002-0000-0ff1-ce00-000000000000"
$P = Get-MsolServicePrincipal -ServicePrincipalName $ServiceName
New-MsolServicePrincipalCredential -AppPrincipalId $P.AppPrincipalId -Type asymmetric -Usage Verify -Value $credValue

This will import the self-signed certificate from the Exchange server into Azure AD so it can be used for mutual authentication.

I did not run the commands mentioned above on my Exchange server but on my Azure AD Connect server since the MSOL module was loaded on that server. For importing the certificate file I had to use the following command accessing the certificate file (instead of the $ENV:System variable):

$CertFile = "\\AMS-EXCH01\C$\OAuthConfig\OAuthCert.cer"

Register endpoints in Azure Active Directory

The last step is to register the endpoints of your on-premises Exchange environment into Azure Active Directory. You can use the following commands to register the endpoints:

$ServiceName = "00000002-0000-0ff1-ce00-000000000000";
$x = Get-MsolServicePrincipal -AppPrincipalId $ServiceName;
$x.ServicePrincipalnames.Add("https://webmail.exchangeserver.com/");
$x.ServicePrincipalnames.Add("https://autodiscover.exchangeserver.com/");
Set-MSOLServicePrincipal -AppPrincipalId $ServiceName -ServicePrincipalNames $x.ServicePrincipalNames;

Instead of webmail.exchangeserver.com and Autodiscover.exchangeserver.com you must use your own local FQDNs of the Exchange server (shown below in the verification screenshot).

You can use the the following command to check if this was configured correctly.

Get-MsolServicePrincipal -AppPrincipalId 00000002-0000-0ff1-ce00-000000000000 | select -ExpandProperty ServicePrincipalNames

As shown in the following screenshot:

Register Endpoints

Note. Over the years I have run the HCW several times. Domains have been added, but not (automatically) deleted in Azure Active Directory.

IntraOrganizationConnectors and AvailabilityAddressSpace

The Hybrid Configuration Wizard created the IntraOrganizationConnectors (both in Exchange 2016 as well as Exchange Online) and configured the AvailabilityAddressSpace. There’s no need to create these, but you have to check them using the Get-IntraOrganizationConnector and the Get-AvailabilityAddressSpace commands)

Verify the OAuth configuration

To verify the OAuth configuration you can use the Test-OAuthConnectivity command. You must do this on the on-premises Exchange server and in Exchange Online.

On the on-premises Exchange server use the Exchange Online Uri and a mailbox on-premises:

Test-OAuthConnectivity -Service EWS -TargetUri https://outlook.office365.com/ews/exchange.asmx -Mailbox onprem-user@exchangeserver.com -Verbose | Format-List

In Exchange Online, use the Exchange on-premises Uri with a mailbox in Exchange Online:

Test-OAuthConnectivity -Service EWS -TargetUri https://webmail.exchangeserver.com/metadata/json/1 -Mailbox Online-User@exchangeserver.com -Verbose | Format-List

The output is an extended list, but in the end you should see ResultType: Success and IsValid:True on your console:

Test-OAuthConnectivity

You have now configured the OAuth between Exchange Online and Exchange On-Premises.

 

Exchange Hybrid, Office365

Outlook 2010 stays offline with Exchange Online

7 Comments

One of my clients is running Exchange 2010 in hybrid mode, and they have Outlook 2010 and Outlook 365 ProPlus client. For testing purposes, I have two VMs, one with Windows 7 and Office 2010 and one with Windows 10 and Office 365 ProPlus. And every Monday morning I run the Windows 7 VM for an hour or so to see if everything is working fine 😊

This morning my Outlook 2010 was working offline, and it didn’t want to go online (OWA and Outlook 365 ProPlus were working fine). Remove the Outlook profile but creating a new Outlook profile didn’t work. After a minute the dreaded an encrypted connection to your mail server is not available error message appeared:

An encrypted connection to your mail server is not available

Mostly this is caused by Autodiscover that goes wrong somewhere, the Remote Connectivity Analyzer shows that Autodiscover to the on-premises Exchange 2010 goes well, but that the redirect to Exchange Online goes wrong and it generates the following error message:

An HTTP 456 Unauthorized response was received from the remote Unknown server. This indicates that the user may not have logged on for the first time, or the account may be locked. To logon, go to http://portal.microsoftonline.com.

And further down more details are revealed:

X-AutoDiscovery-Error: LiveIdBasicAuth:AppPasswordRequired:<RequestId=8a51c25b-9213-4873-aff8-ebc1da40544f>;

An HTTP 456 Unauthorized response was received from the remote Unknown server

The AppPasswordRequired explains more. Last week I changed the MFA settings (see previous authenticator app for Office 365 blogpost). This works fine for OWA and Office 365 ProPlus, but not for Outlook 2010. Since Outlook 2010 does not work with Office 365 MFA, especially not in a hybrid environment (not even with an App Password).

The only workaround here was to temporarily disable MFA for my user account, create a new Outlook profile (which worked fine without MFA) and re-enable MFA. Again, Outlook 2010 does not recognize the MFA and still works with Exchange Online using basic authentication, but all other Office 365 services work fine with Office 365 MFA (both SMS and Authenticator authentication).