Hey, great news! Somebody has finally figured out all the steps required to do PocketPC USB tethering in Linux!! This is huge news.
This should also work for other WM5 devices (perhaps even Motorola Q?) -- although written for PPC-6700 on Sprint using Fedora Core (FC5), there are instructions which suggest how to adapt for other Windows Mobile devices, and it should be trivial to make it work on other distros. It will likely work fine for Verizon, but it would be good to get feedback here.
I've been in touch with the author, he is in process of perfecting it (not necessary to give real user name/passwd, just give something, ie. "web", "web").
Well, here's the link, enjoy!
http://andrewtv.org/fedora-ppc6700/