There are other possibilities - for example they can maintain a list of tainted coins, and declare them illegal to transact. This can then be enforced at the level of exchanges.