Every now and then appears someone with the "new" idea of tainting coins. It's a very bad idea for multiple reasons. God, use the search button and you'll find a lot of threads about tainting.
What we need is an add-on for the Satoshi client and for the usual mining software to allow people melt-mining coins. That way we prevent the next "visionary" to taint our coins.
Melt-mining: mine a block and add a selfmadetransaction with all the coins you want to "melt" as fees. You need a tweaked client that prevents the selmadetransaction to be broadcasted but in your brand new mined block.
BITCOINS MUST BE FUNGIBLE.
I recommend, you read the technical discussion about colored bitcoins:
https://bitcointalk.org/index.php?topic=106449.0You will soon realize that coloring does not embed information with the coins. You have to conform to a strict set of rules for creating a color conforming transaction, which means that color information is very volatile. The apparent advantage of that is that the color information does not require additional bits or bytes. It uses the decreased entropy of the transaction in order to save the color state of unspent outputs.