I went to the Verizon store this evening. The guy there was very helpful. He started out by saying they don't have any iPhones in stock, and the only place to get them now would be at an Apple Store.
Again, this doesn't sound right. Did you go to a corp store or an agent? Agents don't have the iPhone, only VZW Corp stores. All the corp stores around me have plenty in stock and if they didn't they could still ship you one from the warehouse.