Very few people will actually have lost privkeys. Patching your server is a much more important countermeasure than revocation. Certificate revocation in practice works nowhere nearly as well as it does on paper; in fact, it comes dangerously close to not working at all. Read Adam Langley's (jaundiced) take on OCSP for more details.
Long story short: certificate revocation is probably not a big enough deal for Start to somehow be required to rewrite the terms you agreed to when you acquired your certs from them.
I think this is Langley's post tptacek is referencing: https://www.imperialviolet.org/2012/02/05/crlsets.html
I'm a StartCom customer, and I'm going to suck it up and pay to revoke all of my certificates, including several class 2s and an EV. I'm going to do it because it's better for the PKI than if I don't.
Now, StartCom, It would be nice if you'd help us out, too. This is a mess. Maybe we can get a bit of a break. Maybe you can revoke all of my certs for $25. Or maybe it can be $5 or $10 a piece. We want to put you out of business, but come on, we all know signing certs is tantamount to printing money. If the trust model falls apart, you're out anyway, so how about playing an active role in sorting this out?