If you look for reasons to dismiss the idea out of hand, you will find them. However if you use the example to increase your understanding of why some P2P systems succeed yet many more fail, it will give you some insight.
In that spirit, let me answer your questions directly.
What happens when they disagree about which transaction happened first? Majority rule? Who decides what the majority is, and can it change if 4 of the five nodes leave the network and are replaced by another 5 nodes?
If ANY other transaction using that out-point is found there is a double spend, same rules as the current bitcoin system. The only way there can be disagreement is conflicting transactions got broadcast simultaneously but one arrived a close node A first and the conflicting one arrived at close node E first. By the end of the two 5 node broadcasts, both parties would discover the double spend.
So which one is valid? Who cares. Flip a coin. That is exactly what bitcoin does in this situation. If my node is working on a block with on transaction, and your node is working on a block with a conflicting transaction, whoever solves the block first wins. Distributed coin flipping algorithms are trivial. All of this can be done almost immediately. Much faster than in 10 minute windows. So no, the majority doesn't change if 4 nodes leave, because consensus was reached and the nodes were made consistent.
By the way, standard DHTs already address preserving data when nodes leave, and spreading the data when nodes join.
And if I know that I'm going to create a large transaction, can I do some work precomputing node IDs such that the transaction (which I haven't yet sent out) will hash to nodes that I control? If I control all the nodes storing the transaction, then I can just answer "yes, absolutely, that transaction is valid and hasn't been double-spent..."
No, this would be a requirement constraint. It is possible for the same reason that it is impossible to generate two public keys that match to the same bitcoin address. See my previous faux pas.
Nodes would generate node addresses based upon private keys, exactly as is being done for bitcoin addresses. This makes node spoofing implausible. All of the inputs to the out-point hash are fixed except the payee, which is pre-specified. The only flexibility I can think of would be in the payment amount. If you want to iterate through all possible amounts and try to create a simultaneous 5 way hash collision, knock yourself out.
The brilliant insight behind bitcoin is the distributed timestamping mechanism; everybody agrees on an order of transactions. I don't see how your scheme solves that problem.
It actually solves the problem in exactly the same way, just with much less CPU power.
The brilliant insight behind bitcoin's distributed time stamping mechanism is you don't need absolute timestamps at all! You only need relative order. And for conflicts in a short window, you don't have to care at all. You can simply arbitrarily choose one.
My solution does exactly the same thing. It maintains relative order among transactions. It arbitrarily reaches consensus on conflicts. Neither method has a requirement to accurately order unrelated transactions by time. Again, that was a brilliant insight.