There are other ways to track transactions other than the txid, for example by tracking a unique output address. A normalized hash routine has been added recently: https://github.com/bitcoin/bitcoin/pull/3656#issuecomment-35...
Just a naive suggestion (will this work?):
Why not introduce some sort of a 2-phase commit with the original transaction and the newly inserted one on the block-chain? So, before the block-chain transaction is committed, check the two transaction id hashes, if they are different for the request, fail the transaction.
Edit: Of course, the eavesdropper could just as well pass the expected hash back to the originator anyways. :-( Hmmm
The biggest flaw here is probably the name "transaction id", because it suggests that a transaction can only have one valid id. The normalized id fixes this issue for most transaction types.
For those interested in finding out what transaction malleability is:
http://www.coindesk.com/bitcoin-bug-guide-transaction-mallea...
<quote> What is transaction malleability?
It’s an attack that lets someone change the unique ID of a bitcoin transaction before it is confirmed on the bitcoin network. The change makes it possible for someone to pretend that a transaction didn’t happen, if all the right conditions are in place. </quote>
This is a fatal design flaw in any TPS system. From any sound accounting principles point of view, no journal entry is to be manipulated after insertion - only through compensating transactions (referencing the original).