Not sure about the Elites, they are tough to find. Actually when I exchanged my premium it was the last on the shelf. Still, I'd take the giftcard deal rather than wait for something to come back from MS. They should give you a giftcard right in the store too. Even then if they are out of stock, you can go online and buy a new one and have it shipped in a few days. The Elites are supposed to become the new premium anyway, so by the time yours breaks they should be available.
Plus, the big difference is with MS you are only getting a refurbished 360, not a new one. These things are not the most reliable in the world, and you stand a much better chance with a new one.