I understand the word "must" to mean that they cannot add additional strings, such as payment, to their obligation to revoke the certificate. Is there another way of interpreting it that I am missing? I guess you could interpret it as "must provide a mechanism", but I can't see that that was the intent of the original document.

Mozilla's use of the word "must" here I think is important, because the barriers to correctly dealing with a security breach should be minimized. For better or worse, root CA's are entrusted with maintaining the security of large chunks of the internet. Charging users who suspect that their certificates _may_ have been compromised (due to the Heartbleed bug, in this case) will cause users to err on the side of inaction, which is going to weaken internet security in the long run.

Their basic free Class 1 certificates are advertised on their website as “No Charge, Unlimited + 100 % Free” and “No Kidding 100% FREE”.

It wasn’t hard for me to find the provision that revocations cost $24.90 in question 72 of the FAQ, but it’s not exactly highlighted either. It’s probably not something that most people think about; they probably assume that StartCom provides free certificates (and have the automated infrastructure to do so) for publicity and/or to up-sell paid services. And I did actually go to a paid StartSSL service, which I probably won’t renew.

This isn’t to say that I have a “right” to a free revocation, and I should read the fine print, but I think I’m justified in lowering my opinion of their business practices a few notches.