Polycom VoiceStation 500 and Android headsets...a solution...

http://www.amazon.com/Voicestation-Analog-Conference-Phone-Bluetooth/dp/B000GGMLNM/ref=sr_1_1?s=electronics&ie=UTF8&qid=1285368276&sr=1-1

We called Polycom support and it appears to be a known technical issue with the Android stack. You're supposed to click on the Mode button for 3 seconds on the Polycom to pairing mode, which will show the device on the Android phone. However, all you see is the "Pairing but not connected" when trying to connect to the Polycom VoiceStation 500 unit. The issue is observed for both Android v1.6 (HTC Magic phones) and Motorola Droid phones running Android v2.2

Polycom says it is an issue with Google's Bluetooth stack. The latest v2.2 release does not seem to solve this compatibility issue, and there enough reports that the Android Bluetooth stack (BlueZ) has issues pairing with car stereos, keyboards, etc.

For Android-based headsets, you can use the 3.5mm to 2.5mm cable that comes with the Polycom VoiceStation 500. However, the cable that comes with this one has two types of a cable: 1) a 2.5mm to 2.5mm cable (which doesn't work on Droid 3.5mm headset), and 2) a 2.5mm to Y-pronged 3.5mm for computer microphone and output.

If you use the 2nd cable included (and use the green-labeled connection for headset), you can at least use the Polycom for voice conference calls while relying on the Droid headset for microphone input. We're in the process of ordering a 2.5mm female to 3.5mm adapter to see if we can use both the Polycom's microphone/speaker.

At least this solution allows Droid-based phones to use the Polycom, though you're certainly paying a premium for Bluetooth support that doesn't work. The Polycom unit seems to work fine though with iPhone's.

In case you want to learn more about how the Android Bluetooth stack works, here is a slide presentation that I found:
http://www.slideshare.net/erinyueh/android-bluetooth-introduction