Strange credential sync problem on workstation after password reset on AD/AAD hybrid environment.

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, we still have our own DCs that handle AD logon). 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.  I don'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, like below.
   
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.

The problem most commonly happens with users that more than one computer. The following example shows the most common mode of failure:

Sally works on Station 1 and Station 2 at different times and schedules, but never at the same time.  Last week, she worked on Station 2, logging out on Friday, 11/24.  This week, and for the next several weeks, she will operation on Station 1.  She logs into Station 1 on Monday, 11/27, and works as normal.  On 11/28, Sally is prompted by Windows that her AD password will expire within the next 7 days.  Sally performs a CTRL+ALT+DEL and changes her AD password.  Sally will experience the symptoms listed above, and call support (me) to fix.  I fix it by deleting the Outlook profile as described in point 4 above.

In 2 weeks, Sally will operate on Station 2 again.  She will login to the computer with her AD credentials without incident, but will notice that when she starts Outlook, mail will show as last updated on 11/24, and that Outlook is displaying 'Need Password'.  Sally will experience the symptoms listed above, and call support (me) to fix.  I fix it by deleting the Outlook profile as described in point 4 above.

What I need to know is what causes this and how to prevent it.  Is it a policy setting, or perhaps a setting in the Admin Center, or something else?  We have been stumped, and our managed service, which assisted in setting up 365 earlier this year is at a loss to explain it, telling us simply to "Run SaRA."

Some additional stuff we tried:

• 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.
• 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, and blowing away the Outlook profile is faster than running SaRA every time this happens.
• Also, Revoking MFA sessions from within Entra does not mitigate the problem, either.

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