Ich habe es geschafft, es zu lösen.
Ich habe vergessen zu erwähnen, dass mein Computer Lenovo S10e ist, der über einen Broadcom Bluetooth-Adapter verfügt.
Windows 7 schlug immer wieder vor, meine Bluetooth-Treiber von der Broadcom-Website zu aktualisieren, aber das hat nicht funktioniert - die Installation konnte meinen Adapter nicht finden.
Ich bin auf einen Thread in den Lenovo S10-Foren gestoßen, in dem vorgeschlagen wurde, den Broadcom Bluetooth-Treiber für Vista zu installieren. Ich habe die Treiber aus diesem Thread heruntergeladen und vor der Installation die Standard-Bluetooth-Treiber in der Systemsteuerung deaktiviert.
Nach der Installation habe ich versucht, das Headset erneut zu koppeln. Es wurde nicht nur erkannt, sondern auch ein Assistentendialogfeld, in dem ich gefragt wurde, ob ich das Headset mit Skype verwenden möchte. Nach ca. 2 Klicks funktionierte es also. Ich wurde gebeten, BTStackServer in Skype zuzulassen, aber das war alles!