Gundato: It is not up to Valve to make sure they will have enough keys. Codemasters clearly did not expect FUEL to sell that well. It happens.
The problem here is that Valve (and possibly Codemasters) knew they going to hold this sale. And unlike your B&M example, they most certainly could have requested additional kyes well in advance of their planned sale.
As others have said, this is not the first time (nor the second, third or fourth....) that this has happened on Steam. They know the score, they could have avoided it.
And again, unlike your B&M example, they should not have that lengthy a wait for additional keys, the only shipping involved there would by via whatever method they get the numbers into their database. There's certainly no waiting on some delivery guy to hand deliver the goods.
Plus, chances are that the regional restrictions still apply. Since there are different distributors for each region, it is quite reasonable to assume that there would be different people who get paid for the keys. CodeMasters handle all of their releases on Steam and release worldwide (they might by hugely delayed by Valve for some regions, but there are no other publishers involved).
As for a sale, GamersGate are price matching the Steam sale for Flotilla, offering it at 10% off.
In fact, GamersGate seem to be doing a lot of price matching these days.