The problem is that you have no way to verify what may or may not have been done by malicious actors using compromised keys in the meantime.
If you have immutable, permanent audit logs, you can go through all actions authenticated with something directly or indirectly signed by the leaked key. However, building such an audit log in a way that someone with maximum permissions still can't tamper with it is not easy — and not cheap. (And, worst case, the audit log may not have the necessary detail; e.g. just listing an authenticated identity, but not the way authentication was established — thus not allowing easy identification of possibly compromised access.)
As such, the hole in the strategy is that it doesn't account for other persistent backdoors that may have been added while access using this leaked key was possible. It only prevents further exploitation of the issue. But depending on the sophistication level of the attackers — which seems extremely high considering how the key was apparently stolen — it's nigh impossible to figure out how many secondary avenues of access they have established.
* We already have confirmation that the US government has been tapping internet infrastructure, accessing back doors in BigTech backends, and compromising industry-wide encryption and RNG standards.
So there is no way to prove that SOMEONE at the NSA doesn't have the ability to access all of the information on the internet.
And, since the NSA is just more humans, that means there's no way to prove that someone else hasn't sold that ability or specific subsets of the data to malicious actors.
Post Snowden revelations, you have to do risk analysis. Is some US or Five Eyes Government Agency able to access all your personal information or business competitive secrets? Probably Yes. Can one of your competitors? Probably Not. Can a malicious neighbor or drug cartel that would then use it to extort you for money? Probably not.
So even in this hypothetical example where everything authenticated by Microsoft is tainted, it's not clear if it actually changes this equation significantly.
Could this be said for just about _any_ intrusion? Once you’ve been compromised, is there any way to know that no back doors were installed? Is this situation different than others?
Well, it really depends on the maximum privilege achieved by the intrusion, a user getting compromised hopefully can't do much more than exfiltrate data they have access to; local admin could compromise the OS or even the BIOS, then there's possibly multiple levels of domain admin, and then there's a compromise of the authentication system itself…
If you have immutable, permanent audit logs, you can go through all actions authenticated with something directly or indirectly signed by the leaked key. However, building such an audit log in a way that someone with maximum permissions still can't tamper with it is not easy — and not cheap. (And, worst case, the audit log may not have the necessary detail; e.g. just listing an authenticated identity, but not the way authentication was established — thus not allowing easy identification of possibly compromised access.)
As such, the hole in the strategy is that it doesn't account for other persistent backdoors that may have been added while access using this leaked key was possible. It only prevents further exploitation of the issue. But depending on the sophistication level of the attackers — which seems extremely high considering how the key was apparently stolen — it's nigh impossible to figure out how many secondary avenues of access they have established.