I already said as a global mining or payment option checking for dirty coins is fraught with issues. However, for me it would be a nice service I would want, especially when buying on localbitcoins. Before i meet with the guy I will ask for an address for proof of funds. I will check his address to see what the dirty factor is, I can choose to skip meeting him if i want.
I think it would also be a cool app to see how dirty your own coins are.
Your localbitcoins scenario won't work because the bitcoins are sent from a wallet owned by localbitcoins and the seller does not know where they will come from.
Blockchain.info has a "taint" feature that will give the sources of the bitcoins at an address. You can check to see what percentage are from specific addresses.