Hi Moritz,
Can you confirm this is happening with users which have the per-user MFA status Enforced? Per-user MFA has three status (disabled, enabled, enforced).
All users start out Disabled. When you enroll users in per-user Microsoft Entra multifactor authentication, their state changes to Enabled. When enabled users sign in and complete the registration process, their state changes to Enforced. Administrators may move users between states, including from Enforced to Enabled or Disabled.
If per-user MFA is re-enabled on a user and the user doesn't re-register, their MFA state doesn't transition from Enabled to Enforced in MFA management UI. The administrator must move the user directly to Enforced.
You have more information in https://learn.microsoft.com/en-us/entra/identity/authentication/howto-mfa-userstates
Also, check service settings and make sure you are not skipping MFA for trusted IP addresses, or when the remember MFA on trusted devices feature is turned on.
Cheers