There are a few misconceptions in the comments, maybe not everyone fully understood what I was getting at.
- Who is appointed to run the blacklists? Nobody in particular. That's the point. It is or can be a form of community self policing. Silk Road could run a blacklist. The police could run a blacklist. In the eyes of the system they'd be equals. Who pays for them? Depends on the kind of issue we're talking about, right? Any time you have a community that wants some kind of self-policing, there could be such a thing. I doubt it'd be expensive to run. If you want some kind of ultra-libertarian completely privatised police force you could use assurance contracts to pay for them.
- How do we enforce them? We don't. It's up to the users to decide what to do when a transaction is flagged. Rejection is not necessary, you can as well just accept the coins and then inform someone else who can follow up/investigate. If you think the whole system is bullshit, then just don't check any lists or ignore any flaggings if you do. Problem solved.
- What if everyone ends up with tainted coins? Taint can be removed because when it passes through the hands of a nexus that is known to take some kind of useful action on a blacklist hit, they can add their own outputs to the whitelist and the graph traversal stops there. Eg, if somebody steals coins and sends them to Mt. Gox, then Mt. Gox can go ahead and file a police report and then add their own outputs to their nexus whitelist. Wallets stop searching at that point because you trust Mt. Gox to "clear the taint". So it isn't possible for taint to last forever (you'd eventually have to stop searching due to resource usage anyway, even if you don't hit a nexus).
- How can this be used against the innocent? If a blacklist routinely ends up including outputs that are not associated with any kind of real criminal activity (as judged by the person/entity checking it), then it'd make sense to just stop using it. Remember, this is a community based solution. Nobody has the power to centrally stop or block transactions. If your salary ends up on a blacklist intended for identifying money used in the child porn trade, and you're innocent, then you should be able to make a loud noise through the press, etc, and people would realize that this list is being abused. So they'd stop checking it.
Vladimir says, people would just use coin mixing and the system wouldn't work. Yes, indeed, tx graph obfuscation breaks such an approach. At least if they don't take each other into account. It'd be up to the user community to trade those things off. For instance, you could engage in a mix but only accept old coins that don't appear in any of your blacklists.
But there's something to consider - we all benefit from a stable society that isn't overrun by murderers and thieves. If you're deliberately impeding legitimate investigations into real crimes, whether it be by the police or otherwise, you're really just undermining the source of your own wealth. I think most people would understand that.
Here's an example. Let's say there's a blacklist called the emergency response list. It's used only in the most serious and time critical cases. The operator is the police and they ask subscribers to inform them immediately on encountering a hit. Bob the executive comes home from work early one day and discovers his girlfriend in bed with another guy. Enraged, he grabs a hammer and smashes both their skulls in. Realising what he's done he goes on the run. The girlfriends mother comes round an hour later and discovers the crime scene. She phones 911 and says that her daughter is dead along with another man, and Bob has disappeared.
The police ask the mother who Bob's employer is, and they then phone up the employer and ask them for the output set used to pay Bob's last salary. Those outputs are added to the emergency response list. Bob goes into a gas station and tries to refill his getaway car, when he pays the shopkeepers terminal flags the transaction. Bob still gets his gas but once he's out the door, the shopkeeper phones up the police and reports the guys location.
What about someone else who Bob paid money to? Their coins are also tainted. They're in a fashionable chain of restaurants and when they try to pay the bill, their transaction is flagged too! The restaurant owner also calls the police and describes the guy at the table, the response is "ah nope, that's not him", the bill is paid and the guy goes on his way - moderately inconvenienced for a few minutes, but not hopelessly so. What's more, because the restaurant chain is big, well known, and has policies for what blacklists they check and what they do, they are a nexus. When the chain pays its waiters at the end of the day it puts the salary outputs onto its own whitelist and then when the waiter spends his money, nothing is flagged.