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.
That would only be good for unique transactions, and for individual wallets.
If you have User 1 and 2 sending the same amount from Exchange A/online Wallet A to Exchange B/Online Wallet B, and only one transaction goes in the blockchain, whose is it?
And how long do you wait before re-sending the transaction if you don't spot it?
The more you wait, the greater the risk a User 3 will ask for the same transaction, which will just further mess things up, and it wouldn't be hard to exploit your input/output based "simple" transaction check to cause trouble.
A safer solution under the current protocol would be to spam the blockchain by including signature transactions: small extra amounts going to specific addresses known to the exchange, and that are unique (to the exchange) at any point in time. This will cause transaction dust of course, which is its own problem.