AD/AAD Account on Local PC Randomly Out of Whack

I don't know if this is the place for it or not, but I have nothing to lose at this point by asking. Googling results has not been very fruitful for me or my other technicians. So, our business is a hybrid AD/AAD site. We also use Office 365 and enforce MFA thru Authenticator to login to Microsoft applications (but not the PC itself). Recently (within the last month or two), some weird credential breakage has been randomly happening to users, many times after a password change in AD, but not always. Idon't know how to articulate it, so let me describe the symptoms.

1. The start menu indicates that the account information needs to be verified.
2. Outlook disconnects and displays 'Need Password' at the bottom.
3. If you attempt to 'verify' from the OS account settings app or click on 'need password' in the two above cases, the Authenticator prompts pops up (in Windows) for a moment, shows the three thinking balls, and then goes away, having never displayed a number onscreen for the user to punch in on Authenticator.
4. So far, the only way we've been able to mitigate this is to delete the Outlook profile from the Control Panel>Mail settings, forcing a new outlook profile creation. This fixes both 1 & 2 above. When you start outlook, everything, including the authenticator prompt, magically works again.

Additionally, going to office.com and logging in works fine (authenticator and all), but does not pass through to the OS or Office. Restarting the device has no effect. This affects both Windows 10 and Windows 11 machines.

We started troubleshooting with Office at first, until we noticed that Windows account sync itself was bungled up, so that leads me to believe it might be a setting in our Admin Center someplace, but I just don't know.

Have any of you admins experienced this with your environments? Have any ideas?

Edit: Revoking MFA sessions from within Azure does not mitigate the problem, either.

Edit 2: Microsoft SaRA resolved the issue by running a OLicenseCleanup.vbs. So that confirms that something breaks and is fixed by a cleanup operation, but that still doesn't indicate what the problem is or how to prevent it.