The following proposal has been characterized as a horrible idea (see replies), so I thought it would be fair warning to others who explore the idea.

The Personal Blacklist
I propose a new feature called "blacklist".  This feature allows the user to enter BC addresses into his own personal blacklist because they want to know when they receive BC that came from a certain address.  I think the user should also be able to set a threshold so that any transactions from the blacklisted address that are under that threshold would be ignored handled as if they came from a good address. [Added with title change:] The user should also be able to establish a whitelist so that any transactions coming from whitelisted addresses would not be searched back any further.

The Search
Whenever the user receives BC, the feature will search back through the blockchain to find all the transactions that added funds to that address to see if any of them are in the blacklist.  It does this recursively til it finds either an address in the blacklist or all the blocks that created all the BC that ever found its way into the senders address.

The Output
If the generation blocks for all bitcoin are found without finding any blacklisted addresses, the user gets a happy Message.
If an address is found that is in the blacklist then the user gets the following information:
Some of this bitcoin comes from Blacklisted address XXX:

Block#	Date/Time	Amount	Sent By	Received By
#	//::	#BC	XXX	YYY1
#	//::	#BC	YYY1	YYY2
#	//::	#BC	...	...
#	//::	#BC	YYYn	ZZZ

ZZZ is the user's address.

At this point, the user can either request the sender to send non-stolen bitcoins and provide the thief's address to the sender who can add it to his own blacklist, and probably a link to posts on the internet that explain the theft.

This will have the effect of dividing the BC community into those willing to accept stolen bitcoin (either because they don't know, or because they don't care) and those who aren't.

But what if your address holds stolen bitcoin?  That would be detected when you add a thief's address to your blacklist.  At that point, you get several lists just like the one above, one for each sender who has sent stolen BC to your address.  It's up to you to figure out what to do about it.

This proposal only empowers Bitcoin client users to have more information about their counterparties.  I suspect and hope it would grow into a major headache for bitcoin thieves.  It will certainly be a headache for all BC users who have a lot of transactions, but only if people with great goods and services who accept BC decide to refuse service to recipients of stolen funds, and use low thresholds.  So the effectiveness/headache tradeoff is in the hands of the users, where it should be, and the more work we put into it, the more the thief suffers.

Comments?