A Microsoft app for iOS and Android devices that enables authentication with two-factor verification, phone sign-in, and code generation
I believe I recall seeing one similar instance of this in the past, though it was so long ago I'd never be able to find it now and have no recollection of the final situation.
"The only remaining problem was that I could not change the attacker's email back to the primary alias because of Microsoft's waiting-period restriction. I contacted Microsoft Support for help with this."
Contacting Microsoft Support and through them CDOC in order to fix this was your mistake, since no one that I'm aware of within Microsoft can perform manual changes to accounts any longer, especially the original alias, since that policy was put in place to keep previously existing/deleted accounts from being accessed by others, in order to ensure that they couldn't be abused by others re-creating them to access the original owner's 3rd-party accounts.
My guess has always been that it's precisely this sort of confusion within support that's likely part of the reason that Microsoft pulled the Support Agent's ability to make discrete account changes in the first place, since I'm quite sure there'd been many other similar mistakes made by agents in the past, including things like giving control of an account to the wrong person entirely, which showed Microsoft the futility of expecting likely often overworked and rushed agents to perform these functions effectively and accurately.
In fact, it's quite possible that the policy currently put in place is exactly what happened to you, since what you were requesting was obviously not possible, so without a full understanding of the specific requirements placed on these agents, we can't know the exact procedures they're required to perform in such a situation.
Either way, it seems clear to me that your specific request triggered the action, so since there's really nothing an agent could have done to recover the original, deleted alias, the only possible method that Microsoft makes available for this is supposedly via the Microsoft account sign-in helper tool, though I've never heard a specific statement that anyone else has managed to fully recover from the specific modifications you experienced using that tool. However, your description of the 30-day waiting period makes it sound as if that might have been slated to occur, but now we'll likely never know, unless you can somehow manage to reconnect with the backend support personnel to get the account suspension lifted.
Rob