In addition the the random nonce, each block also contains a BitCoin address (newly-generated, used only for this purpose) that the 50 BC reward is credited to if you solve a block. Even if two nodes choose the same random nonce to start at (which is unlikely), they’re pretty much guaranteed to have different BitCoin addresses.
Re: (context post by theymos)
Participants: theymos