Microsoft 365 features that help users manage their subscriptions, account settings, and billing information.
Turns out it was a problem with autodiscover that can be resolved by making a small entry to the registry as follows:
1/ With MS Office closed, open the registry (run regedit for example) and navigate to the following path:
HKEY_CURRENT_USER\Software\Microsoft\Office\16.0\Outlook\Autodiscover
2/ Add a new DWORD value named: ExcludeExplicitO365Endpoint and set its Data value to 1, as shown in the image below:
3/ Close the registry and try to add the mailbox again. This time the autodiscover should work properly and allow you to setup the mailbox.
I believe this will likely be fixed soon but this should hopefully help others out before such time.
* Note to admins: Please mark this as the answer.