MFA catch-22 during onboarding due to registration policy

You don't need to use the registration policy, even without it the users will be prompted to register methods the first time they try to access any MFA-protected app. Also, you can scope a CA policy to the registration process itself: https://learn.microsoft.com/en-us/entra/identity/conditional-access/policy-all-users-security-info-registration 

Alternatively, consider using methods such as TAP for the initial account provisioning.