For starters, that's not how a double-spend works. The transaction id is actually a hash of the transaction itself. If you make a transaction that pays to a different address, you've also changed the transaction ID.
I believe what you are really asking is why can't someone submit a second transaction that spends the same unspent transaction outputs (UTXO's) back themself. In that case, it's not really a matter of which one makes it into a block first, but a matter of which one gets relayed across the network first. Nodes will reject and refuse to relay any transactions which spends UTXO's that have been claimed by another transaction in their mempool. If they received the transaction to the deli first, then they would reject your double spend. Considering the speed at which new transactions get relayed, it would require some very precise timing (and quite a bit of luck) to get a 50/50 split of the network. Even if you could do this, then it it would also be a 50/50 chance that the clerk at the deli would see your first transaction. If his software is monitoring the half of the network that recognizes the second transaction as legitimate, then his cash register will say that you haven't paid him yet.
While attacks like these are possible, they are not easy. It's economics that really provides the protection against these zero-confirmation transaction double-spend attacks. It would cost more of your time and money to set up a crime like this than would offset the cost of your sandwich. Therefore, you won't do it. For larger transactions, it is always recommended to wait for the transaction to be included in a certain number of blocks, 6 being the agreed number for near-absolute safety.