In case you didn't notice, Verizon quietly released the Motorola V710, its first readily-available 1xRTT Bluetooth phone, last week.
I've been reading the boards for mini-reviews, and as far as I can tell, the biggest criticism is that it only supports a limited set of Bluetooth profiles -- primarily enabling headset and modem support -- and specifically not supporting OBEX. This is apparently to allow Verizon to maintain a monopoly on ringtones and other mini-addons (via their "Get It Now" service) for their phones. Nevertheless, if Bluetooth is what you've been waiting for on Verizon, now's the time to get it. 8)