I'm using the basic Palm Treo Wireless Headset (not the newest Palm/Treo branded one) :
Palm Treo Wireless Headset for Treo 650, 700
(Sorry for some reasons the equilvalent link to EverythingTreo's store was not working, so I'm posting the link to another store. Feel free to replace the link mod!)
I've been using it since the days of 650. Now I'm using it with my 700p and it works great.
I'm sure the BT headset experience differs for everyone. Make sure you get one from a reputable store where you can return it easily in case it doesn't work for you.