AMNESTY!
Someone cracked the original cd-key for Windows XP, thus allowing the crackers to generate keys that were already in boxes across the planet. As a result, authentic buyers were left with already used keys, despite they were legitimate buyers, and no XP legitimacy to them.
What did MS do? Amnesty to the lot of them. That's consumer concern to you. Later they contacted all the clients that were harmed and assigned new CD-keys to them, AND ONLY THEN, voided the snatched CD-keys. And introduced a new cd-key system with SP2.
Yes, stolen codes should be voided, but only after you certified the last of your valued costumers. It is the burglars that should be harmed, not the consumers.
Shame if they don't do exactly that.