SE K800i BT headset recommendations ?

I'm looking for a replacement for my HBH-35 headset that has not been
behaving itself for some time (it used to work just fine with my
T610i, but then something happened and I lost the ability to voice
dial, record tags, hold connection reliably, and it's no better with
my new K800i).

Any recommendations much appreciated, especially from K800i owners. I
really just need a reliable headset, but the voice dialling and tag
recording is essential - I only use the headset in-car and must have
reliable hands-free operation.

TIA.

--
"Linux, the choice of a GNU generation."