MFA catch-22 during onboarding due to registration policy

The behavior you are seeing is expected.

The Authentication Methods Registration Policy is evaluated before the Conditional Access policies. Therefore, excluding the corporate network via Conditional Access does not solve the problemthe block occurs at the method registration stage, not at the authorization stage.

In your scenario, there is a circular dependency:

The user needs to register MFA

The only method allowed is Microsoft Authenticator

The user cannot install Authenticator because they have not yet completed registration

Recommended approach

The recommended practice for onboarding in these cases is to use Temporary Access Pass (TAP).

TAP allows the user to:

log in for the first time with a secure temporary method

register Microsoft Authenticator

complete the initial MFA setup

TAP acts as a temporary strong authentication method to bootstrap MFA registration, eliminating circular dependency without reducing security.

About using Conditional Access instead of the registration policy

No. Conditional Access does not replace the authentication method registration policy, as they are different controls. Method registration always occurs before Conditional Access evaluation.