Most major (non-embedded, I suppose) OSes have some framework for periodically updating the certificate store. It's not necessarily a full redeployment of the OS.
Mac OS and Windows both are capable of receiving new root certs via the OS update process. Apple says it updates certs approximately once per quarter:
https://www.apple.com/certificateauthority/ca_program.html
I think there is a pretty strong argument for treating a bad CA like a zero-day vulnerability and "fixing" the problem through a security update that un-trusts the cert. However, to date neither Apple nor Microsoft have been especially aggressive in this regard.
Google has taken a somewhat freer hand towards badly-behaved CAs, but they really only control Android: Chrome uses the OS's trust store, rather than its own (as Firefox does). They could presumably change this, and I'm sometimes unsure why they don't, but I guess it has to do with enterprise-environment interoperability. At some point if Chrome were to become the dominant browser, such that they could dictate terms to enterprise customers rather than the other way around (or if web apps really did take over the world to the point where the keystore outside your browser is essentially irrelevant; cf. Chromebooks), maybe they would reconsider this decision...