If you want quality on a budget then you will need to look at "last years" models. You can find a few out there that were top of the line 2 years ago, but are still great. I have a Samsung Wep200 which is a really nice small in the ear headset. You can get them online now for under $25 and they work great. The only bad part is that the battery life is around 3 to 4 hours of talk time. You can also look at the Jabra BT8010 which has a second piece that turns it into a stereo bluetooth headset. These can be found for under $30.
What ever you do, be careful buying on ebay. Some of the stuff for bluetooth on there is just horrible. Even the "brand name" stuff.