Wow, that is a problem. I now have more sympathy for gox and others as this could easily happen, though they should have had some basic human powered fail-safes to prevent a run-away situation.
The thing is... such behavior was
already known since 2011. People writing software to handle large BTC amount should at least have read the specs, and known that txid cannot be used for tracking purpose.
So as a provider, what information should I keep as the unique identifier for the transaction that would prevent this issue. I guess it would be something easily searchable in the blockchain.
You should keep track of the spent/unspent status of the outputs you used as an input of your transaction. Whatever is the version of the transaction that gets included in the blockchain, the input will appear "spent" if the transaction goes trough.
Additionnally, if you reissue a transaction, you should ALWAYS re-use at least one of the input. So that only one of the two transactions can ever confirm, even if the first one finally gets confirmed after you issued the second.