
At the same time, the AutoDiscover confirmation prompt appears, which we accept.

When we try to add said mailbox in Outlook, a modern authentication dialog is shown.

The affected user has a mailbox with the UPN and mail address which is hosted on said Exchange 2019 organization. There are no Exchange Online mailboxes at all in this tenant, because they've got On-Premises Exchange 2019 (DAG). Outlook is activated through an AD synced Office 365 account with username This account only has an Microsoft 365 Apps for Enterprise license assigned. We have a Mac with the newest macOS and the most recent Outlook version v16.66 (it's evil).

I've just wasted 2 hours trying to resolve the following problem:
