Bitcoin optional fees create transaction ordering problems?
Fundamentally, this is why nobody should be accepting zero confirmations, until the payment has confirmations it’s not really a payment made. This is generally referred to as double spending, as clearly only a single payment can confirm in your scenario. If stores want to accept payments in an unsafe fashion, that’s their risk to bear and insure for. 

Technology like Lightning can be used to make instantly confirming transactions safely if this sort of retail experience is desirable, though this comes with its own hurdles.