The question is how do you verify that coins were actually stolen and not scammed by a site owner

?
Anyone can CLAIM that coins were stolen. Proving it is another kettle of fish.
Yet another point the anti-bitcoin lobby refuses to acknowledge.
Bitcoins are controlled by private keys. Numbers. Information. They are accessed through information.
Someone claiming they had their bitcoins stolen, whether truthful or not, has about as much credibility as someone claiming someone copied their password, and used it to do such-and-such. There's no way to prove there was no collusion, or worse, that there was no theft by an outside party.
Anyone who wants to field an ever-increasing number of fraudulent claims of stolen coins begging for their addresses to be blacklisted, can go right on ahead. I'll pass.
This functionality is built into the bitcoin. Its a fundamental part of bitcoin.
No, it's not. It still just some idea in the minds of some people on this forum, and the fact that you're claiming it's a "fundamental part of bitcoin" just shows how far you're willing to carry this belief in this fiction.
Bitcoin addresses are hashes. They're information. When bitcoins are sent to an address of mine, there's nothing I need to do. In fact, there's nothing I can do to prevent it, regardless of how "unclean" someone claims the coins are.
This is the fundamental design of bitcoin.
For this scheme to reject/return/destroy/whatever "unclean" coins to work, you have to write code. That code has to maintain a blacklist (seriously, a blacklist!) of addresses. It has to check the entire blockchain for any and all links to these addresses in all of your wallet's addresses in each block. It has to DO SOMETHING with the transactions, even if that SOMETHING is to just alert you. (Extra credit: guess what frauds are guaranteed if the SOMETHING is to forward the coins to the "rightful owners'" addresses!)
Then you have to incorporate this code into clients and/or apps and/or websites.
And you have to convince people to use it, and to use it properly, and to maintain their blacklists on their own (you're not looking to centralize a list, are you?)
And then you start begging the government to force it on others when everyone ignores your ideas and refuses to use your code.
I cannot think of a way to remove the possibility of tainted coins from bitcoin without moving to a centralized server like open transactions. If you don't want a taintable currency, run an open transactions server without accounts.
There are no such thing as "unclean" coins. What there are are transactions that can be tied back to addresses that are alleged to belong to thieves. Which, unless we're talking one or two transactions back, doesn't mean much to anyone except to the anti-bitcoiners who are so convinced their good intentions will lead us to cryptocurrency heaven that they refuse to acknowledge the problems with the scheme.
If you want to believe in "unclean" coins, by all means, continue believing, and create code to implement that belief. Pardon us while we choose not to believe.
There are people, like deathandtaxes, that have claimed they will respond to a voluntary, per-user, tainted coin system by spamming the blockchain with bogus transactions. I think this shows the level of maturity we are dealing with.
There are no such things as "bogus transactions" in bitcoin. There's just money moving around. And spam is prevented via transaction fees. If the fees are paid, there is no spam.
And to that point, what's the harm with him sending money to public addresses anyway? It's not as if your scheme falls to pieces if everyone finds they have "unclean" coins in their wallets, right? Oh, wait... maybe that's one of the issues you should be listening to us about in the first place.
And you're challenging
his maturity level?