I proposed a new txid type this morning that would contain only prevout,vout and address,amount pairs. It would only need to be used internally by companies vulnerable to this type of attack and doesn't require 99% of bitcoin users to change a thing. When creating a withdrawal, log the new id and do your lookups based on it when users complain.
The txid you propose could collide, should a spend be made from the same address to the same address in the same amount (a certainly foreseeable circumstance). Non-reuse of addresses after spending from them is simpler, requires no protocol change, and seems to be as Shatoshi himself suggested using the bitcoin protocol.
It cannot collide because inputs (prevout,vout) can only be spent once. Only malleable transactions collide with each other, which is the goal.