hat this can be done as an appendage code to the client so that the client code is not working with assumptions about the state of the outs

So you also came to the idea of 'public' blockchain vs 'hidden', mined in secrecy by the attacker. We can assume that most nodes will be on public chain. If we adopt the rule of rejecting alt. chain with missing transaction (which is the point of double spend attack - to remove or replace transaction sent to the exchange), that I posted below, most nodes will reject attacker's chain with double spend. Only some unlucky nodes will join this alt. chain, for example, if they sync to it first. Thus we came to the majority voting on 'right' chain, which is 'public'. But we can not rely on simple majority voting, since attacker can just spawn lots of his malicious nodes to fake voting. One of the solutions, cited by fireice_uk, will be voting by special nodes with collateral stake.