Consegui resolver isso.
Esqueci de mencionar que o meu computador é o Lenovo S10e, que tem um adaptador Broadcom Bluetooth.
O Windows 7 continuou sugerindo que eu deveria atualizar meus drivers Bluetooth do site da Broadcom, mas isso não funcionou - a instalação não encontrou meu adaptador.
Eu tropecei em um tópico nos fóruns do Lenovo S10, onde foi sugerido que eu instalasse o driver Broadcom Bluetooth para o Vista. Eu baixei os drivers de este tópico e, antes de instalar, desabilitei os drivers Bluetooth padrão no controle painel.
Após a instalação, tentei emparelhar o fone de ouvido novamente - não apenas ele foi reconhecido - também recebi uma caixa de diálogo do assistente perguntando se eu gostaria de usar o fone de ouvido com o Skype! Então, depois de dois cliques, estava funcionando. Fui convidado a permitir o BTStackServer no Skype, mas foi tudo!