I've been using the BU-359 bluetooth for awhile. Lasts for a long time on a charge (pretty much most of the day), gets fantastic reception, and has a USB power port so you can power it via USB power adapter. It has auto-shutoff if you aren't using to save battery power. SirfIII chipset too. I think I paid like $50 total from amazon or something like that.
Not sure about other people's issues, but I've never lost a signal once it's locked in, and have not had any connectivity issues using with my windows laptop, my wife's iphone, my iPaq4700, or my blackberry (I use it mostly w/the laptop and the iPaq). Range isn't great, but I can put it in the back of the truck where the rear area power port is and using the laptop up front, although most of the time I just toss it up on the dash if it's fully charged...it's tiny, maybe 1"x2-1/2"x.33"? you can't even really tell it's there, and no cables!