2)What happens when someone using blacklist A accepts payment that looks clean, only to find out they are now blacklisted on list B? No one could use bitcoin for something like ebay transactions, for fear that the payment they received might be blacklisted by some list.
2. The situation is the same as if someone irl where to accidentally purchase stolen goods. Or as if you where accidentally spamlisted because you forgot to secure your smtp server. Your options would be:
a) Return the bitcoins and clear your status. b) Argue your case with the operators of blacklist B. c) Ignore your blacklisting and just don't do business with those who follow blacklist B. If they blacklist addresses for frivolous reasons, more people will ignore their list and it won't matter if you are on it or not.
A decent client could automatically keep the blacklists updated so it would hardly be any burden for normal users.
While such an attempt should increase trust, this mechanism could be used to destroy it.
It could work almost exactly like Spamhaus which tracks email spammers (which coincidentally also happens to be pseudonymous) and smtp servers relaying spam.
As long as enough people opt in to the blacklists it would make life very hard for thieves. Whoever controls the blacklist would gain a lot of power yes, but since opting in would be voluntary you could always decide to use a different blacklist.