Perhaps this is illegal already - under local handling of stolen goods laws. People would likely be inclined to take up this policy were there a single case of legal enforcement.
I believe this would lead to a stable situation where those known-stolen bitcoins were worth far less than regular bitcoins.
The present loud reaction would become irrelevant. What's more, I believe it would benefit bitcoin to remove some of the danger of (irreversible) theft.
That said, tainting is not a path we want to go down. The potential for abuse is enormous, and rendering more and more coins useless.
Think transaction into a bank account : you cannot separate the money that was transfered in from what was already there.
We can taint accounts, but not individual coins.
Say there's a 50 BTC untainted wallet, and tainted 1 BTC is transferred in, then 1 BTC is transferred out. How do you decide whether that outgoing 1 BTC was drawn on the tainted portion or the untainted portion of the account?
If all transactions are public, in theory you could trace user, who has your bitcoin now. Than you could sue him to get your stolen stuff back.