Is this when green addresses come into play? The convenience store trusts transactions from mtgox addresses not to attempt double spending so they accept a 0 confirmation payment?
Well, SatoshiDICE did exactly what a merchant that accepts on 0/unconfirmed will likely need to do ... become discriminating on 0/unconfirmed. Fireduck changed which 0/unconfirmed bets will be processed:
I've set it to allow unconfirmed as long as they have a fee and are based on confirmed inputs.
So the "spam-like" payment that was originally sent to SatoshiDICE will no longer be processed (it will sit unprocessed until it gets one confirmation).
Just to be clear, it isn't easy for one to send a payment and then "accidentally" spend the same funds to somewhere else except with the second time include a fee that happens to cause the second transaction to get included in a block over the first. That is fraud -- which might be why Fireduck offered to let people test this approach against a version of the service for testing purposes:
So the chances of getting caught double spending to defraud SatoshiDICE are low, as bitcoin has user-definable anonymity (hat tip to Jon Matonis for defining it that way). But buying a candy bar and double spending those funds is probably not something you can do anonymously.
I don't know that Green Addresses are the approach to get behind. What I think this proves though is that a merchant that likes to DIY will be more at risk than one using a payment processor that can figure out how to combat these types of risks.
I wonder what would happen though ... where let's say I'm at a merchant and I pay with bitcoin but the payment processor flags it as a high risk payment because it included 2K of data and I didn't pay a fee. The Bitcoin.org client doesn't let me do that but with Blockchain.info/wallet, for example, I could do that.