The Jawbone seems to be all the rage these days. It has auto adjusting volume, and also pretty much cuts out background noise, well, according to them anyhow.

I personally haven't tried one, as my current headset is the Apple made in ear one. It's been one of the first headsets I can stand to use for a while, the over the ear ones never work well for me for some reason.