I called Verizon directly and placed an order- they delivered via FedEx overnight for an additional $15. Phone was ordered on Friday the 13th (spooooky) and it arrived at my work address on Monday.
The Verizon store down the street had shrugged their shoulders when I asked them when they were getting their first shipment. Hah.
Got the number to call from this story:
http://abcnews.go.com/Technology/ZDM/story?id=754987
"The Verizon Treo is not currently available in stores, but can be bought from Verizon Wireless over the phone by calling 800-922-0204."