I recently picked up a moto HT820 from ebay. Criminally cheap (less than 30 euros including shipping) and great audio quality. If A2DP gets better, this headset is gold. Big plus is that you can also use with wire (ask your ebay seller whether the wire is included!).

For me the headset is comfortable enough, but there are people out there who disagree, so I guess this is kinda personal.