@Alejandro Sastre Admin Did a quick repro at my end with one of the test users in my tenant, passwordless authentication worked fine.
Apart from the steps which are mentioned in the above article, I tried the following step - After adding the account in the authenticator app, selected the account - choose the option to enable phone sign-in - which will register the device in Azure AD (will be seen in the user's profile something like below screenshot)
Once the device is registered, try to login portal.office.com and verify the experience, if the issue still persists, lets connect offline to discuss the same.