It is not even clear that the malleability problem is solvable. Besides the problem that there is innumerable ways to transform a transaction to give it a different hash without affecting scriptSig validity, it is simply unknown whether it is possible to algebraically transform an elliptic curve signature without invalidating it. If so, then no matter what you do to cover up the other holes, that gaping one is left open.
Transactions are malleable. Deal with it. If a transaction is observed on the network that has the same input outpoints and the same outputs, it is the same transaction, and mtgox should treat it as such. This is a simple check to do, and trivial to automate.
And instead of reporting only the hash to the user, they should record, report, and track the transaction itself. You should be able to go to your withdraws and see the actual transaction, including which inputs were used, and what the change address is. You can then go to any block chain service and verify for yourself if/when those same outpoints are spent in a modified transaction.
This is MtGox's problem, not bitcoin's.