Not a Nokia one, but I did use the Jabra BT250 for a day, then I returned it due to poor quality. It was strange, as I thought they were supposed to be a good brand, but nonetheless, I got rid of it.
Now I use a BT kit in my car, and the quality isn't that great either. I'm starting to suspect the N95 as the problem...
Anyway, those new bluetooth over-ear headphones from Nokia look great (
http://europe.nokia.com/A4487162 ), but they aren't released yet.
Other than that, the Jawbone (
http://www.jawbone.com ) is supposed to be the bees knees of bluetooth headsets, but they are a tad on the big side. I haven't seen one in the flesh though.