>If the CA or any of its designated RAs become aware that a Subscriber’s Private Key has been communicated to an unauthorized person or an organization not affiliated with the Subscriber, then the CA SHALL revoke all certificates that include the Public Key corresponding to the communicated Private Key.

There is no "if you pay them" condition to that. CAs are not supposed to make, or allow to stand, any signature on a compromised key—period.

Startcom's refusal to revoke all compromised public keys communicated to them after Heartbleed, and in fact their practice of charging for any revocation in general, is not in compliance with the baseline requirements for a CA.

As a result, Startcom should be removed from all browsers as a trusted CA. Let's Encrypt would be a very good replacement, especially if they also offer keys using ECC P-256 (and perhaps a subsequent replacement ECC algorithm).

> A certificate will be revoked when the information it contains is suspected to be incorrect or compromised.

and

> The subscriber’s key is suspected to be compromised;

>The technical content or format of the certificate presents an unacceptable risk;

They are not without fault, but they've much good for open source project and the like, and don't deserve the bad rap thrown at them in every thread that mentions SSL.