To me it sounds like maybe they detected a successful credential stuffing attack against the accounts and locked them. That said, it sounds like their recovery process leaves a lot to be desired.
Locking accounts for "security reasons" and requiring a phone number is a common tactic to harvest phone numbers for "growth & engagement" reasons. Twitter does that since a while ago and recently got caught "accidentally" using those numbers for tracking reasons.
The security argument doesn't make sense because if they don't already have an existing phone number to compare to, they can't authenticate the newly-provided phone number - if the account was actually breached, the attacker will trivially bypass the restriction by just providing a phone number they control and take over the account anyway.
From a security standpoint, the point of requiring a phone number is to increase the expense of the request -- like a captcha.
(Not to say that there is a real security purpose in this specific case.)
This isn't a recovery process as Microsft doesn't ask you to reset credentials and claims to not keep the phone number associated with the account.
This is some sort of incredibily user hostile anti bot technique.
And how providing a phone number can help Microsoft to distinguish a real owner from an attacker?