As someone who is just planning to publish signed desktop software for Windows, this is deeply worrying. What reasons could there be for cancelling a certificate, especially when it has been used for years and the identity is already established?

Are there some ways to combat such decisions legally?

We can still install, right? It just comes up with a scary warning. Still not great but at least we aren't locked out.