Surely, with out even needing to modify the bitcoin client or protocol an easy solution would have been to monitor the inputs of a transaction when a user withdraws. Then, if a user ever claims they didn't receive the funds, mtgox can just check the inputs and follow them through the block chain. Assuming the date, receivers address and withdrawal amount are the same, and only the transaction id differs, you could quite easily determine if the user received their funds or not - and even identify the new transaction id.