This scenario could be handled nicely with the concept of listening nodes:
Transactions are nearly
instantaneous. It's traditional
network confirmations that require tens of minutes. However, as explained by Satoshi, merchants can significantly reduce the probability of a double-spend through the use of a listening period:
https://en.bitcoin.it/wiki/Myths#Point_of_sale_with_bitcoins_isn_t_possible_because_of_the_10_minute_wait_for_confirmationhttp://forum.bitcoin.org/?topic=423.msg3819#msg3819The longer the listening period the greater the assurance that the transaction will be confirmed as is. 10-30 seconds would probably be sufficient. Theoretically, it's possible that the attacker might have a huge cache of hidden miners that would only accept his version of the transaction. But this seems highly unlikely and a huge waste of effort for skimping on a simple meal. It's so much less likely that a payment processor offering the listening node service could likely guarantee the restaurant's payments for a fee far less than what banks charge for the use of credit cards.