My old Motorola bluetooth head set was becoming harder and harder to hear and didn't handle car noise very well. After looking around I finally settled on a Jawbone-2 which was the current Jawbone head set until the Jawbone Prime was just released.
The best price I found, at the time I ordered, was at Newegg.com.
So far it works well from my side. While I'm in the car I've left voice mail messages with car noise including the AC on high and the radio on. I listened to the messages later from home and they seemed clear enough. It seems to work well.
I selected the replaceable pieces (ear loop and ear piece) that gave the best fit. I'm trying the (leather?)-covered ear loop now.