So this all makes me wonder if there is a way to create a central database about fraudulent transactions, and associated addresses. Someone would make an entry into such a database and provide contact information or other community based details, perhaps sign them with a key that they use as a part of transactions on bitcoin-otc/IRC.  Then, when someone else who cares and receives a payment with these bitcoins from someone else, they can contact the original person to get details and perhaps deny the sender the goods/services they're trying to purchase with the stolen bitcoins.

Yes, it would take an outside database, and yes it would take a strong community with reputation and social trust, but it could be helpful.

One example of such a database for Laptops/computers is: http://www.stolencomputers.org/home.html. 

Access to a database for bitcoins would come as a plugin or add on for a user to install on their bitcoin server.