Eventually all messages are put in a sequence. The key word is "eventually".
Let's say there are two users A and B trying to spend a transaction at the same time.
A's transaction reaches Node1 and B's transaction reaches Node2.
Both nodes include the two different transactions in a block and are able to mine the block using those transactions.
Further, when Node1 receives B's transaction it is rejected as a double spend and when Node2 received A's transaction, it is rejected as a double spend as well.
At this point Node1 and Node2 are working on different chains. This needs to be resolved, and the following explains how.
Now, when Node1 and Node2 broadcast their mined blocks to the network, there will be two competing chains. Depending on the which chain other nodes are using you will get 1 confirmation for the transaction from different nodes. That is why spending transactions with 1 confirmation is not too clever an idea.
Eventually, both nodes will reorganise as more blocks are mined top either Node1 or Node2's block. The issue will be resolved when one chain outputs 2 or more blocks more than the other. The losing chain will be discarded by all nodes (who must accept the longest chain as the most valid). At that point the double-spent transaction that did not make it into the valid chain will be invalid forever.
Hope this helps.