Upon a customer's claim of a failed withdrawal or upon timeout, create a new transaction to an internal exchange-owned address using the same prevtx outputs that the (allegedly failed) withdrawal tx used. Once this transaction is sufficiently confirmed, the exchange can trust that the customer's withdrawal did indeed fail and can now safely credit the customer's account without fear that the transaction (mutated or otherwise) could ever be subsequently accepted on the blockchain.
Using this approach, the internal transaction would not confirm if any of the prevtxouts had been redeemed and therefore would be flagged for a human to intervene before re-crediting the attacker's account.
To quote the owner of Mt.Gox:
In other words, "it's too slow to do it correctly, so we'll just give away our money instead."