This is a "cross post" from here, as the "docs" avenue seems dead - in comparison to what the TechNet forums used to be like.
The gist of it is that members of the "User Administrator" group/role can no longer correct a user's ImmutableId.
One development after the original post above is that MC296614 came through the Microsoft 365 Message Center, and pertains to changes to the User Administrator role. While it specifically relates to the fiddling of rights around MFA, I can't help but wonder if either something else impacting ImmutableId was either stuffed up or slipped in unannounced?
There really should be some kind of change log on docs.microsoft.com on RBAC adjustments so we're not left guessing/assuming like this.
If anyone else knows more about what has changed with respect to setting ImmutableId, I've love to hear about it! In the meanwhile, I might knock up a test case in my own tenant and see if it's still an issue (confirmed: it's still an issue).