I am not providing an answer here but I am elaborating on a small discussion with @eth which is relevant to the OP's question, and I wanted to share what I have learnt, thanks to @eth and a bit of reading around.
The misunderstanding that I had was that all nodes execute code when a transaction invokes that code, and therefore assumed that the result of the execution of the code was then circulated to the network, collected and mined into a block.
This process of transaction, transmission, collection and mining to confirm, is how bitcoin blockchain works, but it is not how ethereum blockchain works and is the reason why I misunderstood why double-spends are not possible on the ethereum blockchain. The mechanism is not immediately obvious, so I wanted to explain it.
In ethereum, it is true that all nodes execute the code, but this is especially true of mining nodes. Each mining node determines the transactions it wants to execute and as it executes them it is also searching for the next block at the same time.
This means that when a mining node is lucky enough to discover the next block it has already chosen the transaction that has won and it will not execute two competing transactions with the same nonce.
In other words any given address and nonce combination can only be executed once per node and if, on the occasion it is executed, and the node is successful at finding the block the nonce would be incremented. This would cause all other nodes to reject the competing transaction because the global registry of addresses and nonces, would say that the nonce was too low, thereby excluding all double spend attempts.
I hope this helps others understand why this works.