I have been using bluetooth dialup with my Verizon phones for about 3 years now. There are a few apps that you can pay for to get it working but I suggest to first google for ICS or Internet Sharing application. This can be found on xda-developers website. The problem is Windows Mobile includes this app but Verizon removed it. I just downloaded and reinstalled the .cab.
I use my bluetooth dialup with my eeepc (linux) and I have an HTC Vogue (xv6900) with WM6.1. I started using the bluetooth dialup with a Samsung i730. It also works using the USB cable. I used to pay for Verizons Broadband service until I found that I get the same speeds and that I don't need to pay for service for internet sharing. I do however have the unlimited data plan which will prevent you from paying a whooole lot due to data usage. That can rack up real quick. But the unlimited plan is still cheaper than paying for the tethering service.