Maybe you should wait a month for the new Motorola H500? I too am in search of one. I did order an 810 to try. At least one reviewer on Amazon thought it paired well with the 7100.
http://www.infosyncworld.com/news/n/5858.html
810 update
I have used it about two weeks now including walking on busy streets and with my car window open. I have a Cingular 7100g with latest software. The one feature I love is how opening the boom turns it on and off. I looked at a friends Logitech Mobile Freedom which has gotten good reviews. His BB rang and the headset was in his pocket. He had to fish it out to talk. He had FORGOTTEN it was on. I am finding that for my uses the 810 is working great. No pairing issues and volumne is enough. Most of my use is in a car with closed windows, in my house or a hotel. Since BT implementation is limited on the BB this seems to work for me ok for now.