I had to revoke my wildcard cert a few weeks ago. You can tell them why you did that. As far I know they decide to charge you on a case by case basis. When I revoked my cert I got an email 3 minutes later saying: "Revoked free of charge".
"Class 1 certificates aren't revoked free because we receive too many requests
daily (specially for the Class 1 free certs) and would we have revoked them
all, our certificate revocation list (CRL) would have been blown out of every
proportion."
In a further back-and-forth, the admin proceeded to tell me how much bandwidth I would cause them (I don't even care about being added to a CRL for a personal domain).
Edit: Sorry, you did say a wildcard cert, which sounds like a paid cert, so would offer more "service" I'm guessing.
Their verification service is annoyingly rigid. Anything other than a phone call to a number listed on a phone bill (and no fair blacking out other numbers on a family plan, for instance) or waiting a couple of weeks for a letter from Israel is rejected, even when the information is easily verified using online government databases[1].
1 - Not an NSA joke, more that "hey, voter registration and property tax rolls are public and online; you could just verify that, no?"
Live within their means, or it will cost you $25 (because of "revocation costs").
StartCom are pretty awesome, but be aware of potential pitfalls.