We also have the same problem. I tested various combinations and could identify that passwordless MFA is only working when the affected users are already enabled to use passwordless sign in.
This means they configured their MS Authenticator with this option:
When I applied the policy to a user that already had a functioning MS Authenticator connection but WITHOUT passwordless authentication enabled in MS Authenticator, the user gets stuck in the loop.
But when the user already enabled passwordless authentication in MS Authenticator, he could pass the authentication and login without getting stuck.
Although I also would have expected otherwise, Microsoft does not seem to cover migrating users who are not in passwordless mode yet to the passwordless state by a nice prompt during the auth flow when choosing passwordless MFA. Instead, the policy just requires all affected users to be passwordless already - otherwise they will get stuck in the loop.
Have you ever figured out how to cope with this issue? The insights I gained are practically making it impossible for us to use passwordless MFA since new users who need to setup their MS authenticator app for the first time during onboarding are not passwordless and would therefore always end up in the loop.