Thanks for reaching out to Microsoft Q&A
I understand that the trigger for the MFA to be prompted is the Conditional Access, but besides the fact that this feature is still in Preview, it also has some limitations.
https://learn.microsoft.com/en-us/entra/identity/conditional-access/controls#known-limitations
There are some reasons why you are seeing this behavior, and considering that M365 apps uses Oauth as an authorization protocol, which means that it works with refresh tokens concept, one of the reasons why most users do not have the problem might be because they have a PRT (Primary Refresh Token) and the non-working user might not have it.
https://learn.microsoft.com/en-us/entra/identity/devices/concept-primary-refresh-token
If that's not the case, I'd suggest you look closer to the failing user's sign in logs and try to identify any patterns that are different from the users that are working as expected.
Thanks,
Fabio