I have the same problem with a headset I got from ebay:
http://cgi.ebay.com/ws/eBayISAPI.dll...DLVI%26ps%3D54
It works awesome when I first pair it, including the AVRCP (allows you to skip songs using the controls on the earpiece). But it doesn't pair again after that. I end up deleting the profile and then pairing it again. I was going to return it, but it sounds like it might be the device after reading this thread. A dongle program is NOT a good way to go, since it just relays the audio through the hands free profile. You can see the icon at the top of the screen and it is supposed to use audio through the wireless stereo profile, not the hand free profile. I presume this would also not take advantage of the AVRCP profile.
Any ideas? Please help!