I'm not entirely sure on this, but here's what I remember. They're able to send the BTC back instantly because they use the Bitcoin you sent as an input. If a single input is invalidated, it invalidates the entire transaction, therefore if an invalid output is sent to satoshidice, the output they send back to you will also be invalid. It's protection. At least, that's what I remember hearing, though I'm not 100% on that. It should be comparable with any service where they send instant return transactions.
Isn't that what I said in the OP? My question was, considering you'd know instantly if you won/lost, couldn't you submit a transaction with a higher priority back to yourself, so, you get the money back minus a
MUCH smaller miner fee?
Huh, that makes sense. I guess I was thinking of this in a different fashion. There has to be some sort of safeguard against this. I can't test this, since it'd be expensive to, but it's possible that Satoshidice looks for duplicate inputs in blocks. This should provide some protection against double spends.