Easiest solution is to just taint any wallet that has ever had a coin from a known tumbler added to it. It's harsh and a malicious tumbler could mess up famous wallets, but easy to implement and "safe" to a point.

A harder solution only allows them to withdraw up to the number of coins you can verify were not tumbled. So if some malicious tumbler deposits 0.000001 coin in your wallet you can convert all but 0.000001 of your wallet's value at an exchange.