I have two headsets that work GREAT for me... Overall, my favorite is still my Motorola S305 bluetooth headset. They sound pretty good and they work GREAT for phone calls too. Callers tell me they hear me better with these than they do when I just use my phone. They appears to work great with both my Motorola Droid and with my Samsung Galaxy Tab alike. The other pair I really like, out of my collection of bluetooth headsets, is my Samsung SBH600 Noise-Canceling Bluetooth Headset. They suck miserably at phone calls (the microphones are terrible) but the audio quality for listening to music or podcasts is incredibly good! PLUS, this headset can also with with a 3.5mm plug as well, so it's not JUST for Bluetooth and can use them with my Nintendo DS, in addition to the Androids.
You know--I kept reading that it supported BT mouse and keyboards, and I could never get mine to do it.. and I didn't see anything about Verizon gimping it up, but I can certainly confirm that mine will pair with my BT keyboards and mice, but it refuses to USE them. Anyone know if there's a way to get the Verizon version of the Tab to support them?