Error 121003 on relog attempt

%3CLINGO-SUB%20id%3D%22lingo-sub-1190478%22%20slang%3D%22en-US%22%3EError%20121003%20on%20relog%20attempt%3C%2FLINGO-SUB%3E%3CLINGO-BODY%20id%3D%22lingo-body-1190478%22%20slang%3D%22en-US%22%3E%3CP%3EWe're%20using%20a%20hybrid%20environment%2C%20so%20cloud%20that's%20connected%20to%20a%20on-premises%20domain%20controller.%3CBR%20%2F%3E%3CBR%20%2F%3ENew%20rollout%2C%20still%20underway.%3CBR%20%2F%3E%3CBR%20%2F%3EOne%20of%20my%20users%20just%20reported%20they%20had%20to%20log%20out%20from%20Office%20on%20one%20of%20his%20machines%20(%232)%2C%20and%20can't%20log%20in%20again%20-%20gets%20121003%20and%20a%20message%20about%20password%20update%20not%20being%20allowed.%3CBR%20%2F%3E%3CBR%20%2F%3EI'm%20on%20the%20fence%20here%2C%20because%20machine%20I%20issued%20them%20(%231)%20is%20a-okay%2C%20but%20he's%20a%20%22C%22%20and%20wants%20to%20get%20into%20his%20mail%20from%20his%20private%20device%20(%232)%2C%20too.%20There%20was%20no%20problem%20with%20that%20so%20far%2C%20and%20most%20interestingly%20he%20is%20still%20logged%20in%20and%20works%20normally%20from%20Firefox%20on%20%232%3B%20the%20only%20one%20balking%20is%20Edge%20on%20%232.%3CBR%20%2F%3E%3CBR%20%2F%3ESomewhere%20along%20the%20way%20same%20error%20was%20shown%20when%20they%20tried%20to%20launch%20Teams%20on%20%232%2C%20but%20I%20managed%20to%20brute-force%20this%20-%20I%20located%20cache%20for%20Teams%20app%20on%20his%20work%20machine%20(%231)%20and%20copied%20it%20over%20the%20said%20cache%20for%20Teams%20on%20his%20private%20machine%20(%232).%20After%20a%20restart%2C%20Teams%20stand-alone%20launched%20without%20any%20issues.%3CBR%20%2F%3E%3CBR%20%2F%3EI%20resetted%20Edge%2C%20cleaned%20up%2C%20clean%20booted%2C%20still%20the%20same.%3CBR%20%2F%3ESadly%2C%20search%20engines%20seem%20to%20associate%20Error%20121003%20with%20....solitaire%20on%20xbox%20%3A)%3C%2Fimg%3E%3CBR%20%2F%3EI%20am%20mystified%2C%20why%20would%20anything%20%22think%22%20user%20is%20updating%20password%20when%20they%20are%20merely%20trying%20to%20log%20in%20with%20the%20password%20they%20know%20and%20use%20everywhere%20else%3F%20Why%20wouldn't%20it%20work%20in%20Edge%20when%20it%20does%20in%20Firefox%3F%3CBR%20%2F%3E%3CBR%20%2F%3EBy%20the%20way%2C%20the%20password%20is%20there%20in%20the%20relevant%20place%20of%20Web%20Credentials%2C%20always%20was.%3C%2FP%3E%3C%2FLINGO-BODY%3E%3CLINGO-LABS%20id%3D%22lingo-labs-1190478%22%20slang%3D%22en-US%22%3E%3CLINGO-LABEL%3EMigration%3C%2FLINGO-LABEL%3E%3CLINGO-LABEL%3EOffice%20365%3C%2FLINGO-LABEL%3E%3CLINGO-LABEL%3ESecurity%3C%2FLINGO-LABEL%3E%3C%2FLINGO-LABS%3E
Highlighted
Occasional Contributor

We're using a hybrid environment, so cloud that's connected to a on-premises domain controller.

New rollout, still underway.

One of my users just reported they had to log out from Office on one of his machines (#2), and can't log in again - gets 121003 and a message about password update not being allowed.

I'm on the fence here, because machine I issued them (#1) is a-okay, but he's a "C" and wants to get into his mail from his private device (#2), too. There was no problem with that so far, and most interestingly he is still logged in and works normally from Firefox on #2; the only one balking is Edge on #2.

Somewhere along the way same error was shown when they tried to launch Teams on #2, but I managed to brute-force this - I located cache for Teams app on his work machine (#1) and copied it over the said cache for Teams on his private machine (#2). After a restart, Teams stand-alone launched without any issues.

I resetted Edge, cleaned up, clean booted, still the same.
Sadly, search engines seem to associate Error 121003 with ....solitaire on xbox :)
I am mystified, why would anything "think" user is updating password when they are merely trying to log in with the password they know and use everywhere else? Why wouldn't it work in Edge when it does in Firefox?

By the way, the password is there in the relevant place of Web Credentials, always was.