I visited the Verizon store yesterday to learn more about their PocketPC Phone. Verizon offers the Samsung SCH-I700 PocketPC phone which, to me, is the best device on the market today. I saw the device in the store. It's fairly slim, small and light for the functionality it packs (PDA, phone, camera, etc).
The price of the phone is similar to the Hitachi G1000 that Sprint offers - around $600. I was ready to purchase until I checked into the monthly service fees. Verizon, like T-Mobile, offers a calling plan and then you can add internet access to the plan. T-Mobile's internet add-on runs about $20 per month. Verizon's internet add-on runs $80 per month. A huge disparity there. The total monthly charge for Verizon (calling plan plus internet) would run around $120 per month, compared to T-Mobile's $60 per month.
I may go with T-Mobile, since their phone is the only one running the new Pocket PC 2003 Phone Edition and their monthly service is reasonable.