But they are traceable. There is a public record of every wallet address the bitcoin has touched. If those who it was stolen from reveal their wallet addresses, it should be possible to track down the coins and find out who the thief was.
One could imagine people still choosing to trade in these Bitcoins, but that such a penalty would forevermore reduce their value next to "unshunned" coins. Could legit businesses and people using Bitcoin collectively reduce the value of stolen Bitcoins in this fashion to discourage it without directly discovering who misappropriated them...?
Also, this is ignoring the entire problem of 'who decides what stolen means in a totally decentralized protocol?' That's non-trivial in and of itself.
It's a democracy. If the masses decide that Blockchain.info is blocking coins that weren't stolen for some nefarious reason, they can just ignore their warning.
The question is: do the majority of bitcoin users even care if they are using stolen coins?
It'd likely be along the lines of anti-spam lists. You might have one that's high-profile thefts or seizures. For that matter, these lists could be political, issue-based, or whatever.
It's ridiculous and unlikely to be followed if taken out to the extremes of issue-based disputes, but I don't think it's impossible for a significant number of people to agree not to transact in stolen Bitcoins, some on principle, some as self-preservation (the exchanges), and most because their utility is reduced by the first two groups refusing them. This also happens to increase the value of untainted Bitcoins.
This is the mechanism I always thought the feds would use to go after bitcoin. "Possession of stolen property" - My understanding of the law in my area is that I am breaking the law if I possess stolen property, even if I can prove that I obtained said property legitimately and even if I couldn't reasonably be expected to know that said property was stolen.
What if the feds decided to apply the same thing to bitcoins? I mean, what if you legitimately obtain bitcoins that are, in fact, stolen property? Or bitcoins that were used in a law-breaking transaction?