Can stolen or otherwise tainted coins be laundered through mining fees?
I cannot look into the chainalysis code but if someone cooperates with a miner by paying unusual fees with tainted coins then the high fees are suspicious and I'm pretty sure analytics will monitor this.
Usually it's not a question whether or not the funds on a bitcoin address are from a criminal source, it's a question of what % is polluted. If you go inbound in the transaction trees of an address back to the miner rewards then you might have 1000 addresses and a little percentage will be polluted. So e.g 1.5% of the starting addresses funds are from a criminal source. It's the same with the bills in your wallet or with your ancestors. Going 10 generations back we have upto 1024 great...grandparents and if 10 of them were criminal then we could say that 1% of our ancestors were criminal.
So the criteria aren't the same at all exchanges but I assume that only addresses with a relatively high percentage of pulluted 'ancestors' will be rejected otherwise the exchange would have to stop it's business.