@dawid.matuszczyk does it related to Package Plan? I setup and tested on Free Plan Tenant before go to the paid Production tenant.
Last time I setup on Email factor, and it work on Free Plan but now it didn’t even with Email factor.
My setup on last time on Email: MFA Email factor failed for second time