I'm surprised a bitcoin evangelist like Andreas didn't say anything about the utter fatuity that is "tainted coins". The things he explained is what's a tainted coin and how to make them "clean" by doing K+1 hops, which is not the kind of behavior I'd expect from him. It'd be much more reasonable to say "Don't deal with folks who don't want your privacy", instead of "This is how you'll deal with folks who don't want your privacy".

So, what happens once exchanges begin requiring more stuff to mark your coins as "clean"? What if despite K+1 hops, they also want from your transactions to not be included into the same block(s), as that'd show you're cheating? What if they start asking you to tell them where did you find your coins? Et cetera.

You shouldn't try to make them "clean", but refuse to accept they're tainted, which means, to say no to the exchange.