Aqui há tempos tive um problema semelhante. O adaptador só vinha com o Bluesolei e por consequência não tinha "My bluetooth places" o que é incrivelmente limitativo e estúpido.
Enfim, na altura consegui trocar os drivers do adaptador, de forma que quando o Sistema operativo o instalasse julgasse pertencer à Widcomm stacks.
Ultimamente com esse mesmo adaptador e com as novas versões do XP nem tenho tido problemas nenhuns. Basta ligar e o sistema reconhece, usando assim os drivers por defeito do XP.
É precisamente isso que te aconselho. Desinstala tudo, retira o dongle, volta a ligar e deixa que o sistema o reconheça. Esqueçe qualquer CD que venha na caixa. À partida o rato depois deverá instalar-se normalmente.
Por curiosidade tb tenho um rato por BT da Trust, e funciona tanto no portátil que já tem BT de origem, como do desktop que tem o tal adaptador que te falei em cima.
EDIT: lol só reparei que escreveste que o próprio PC já vinha com o bluesoleil! Mas que estupidez... o Bluesoliel é um cancro!!
Vais ter que tentar desinstalar apenas essa "bosta", e copiar os drivers bluetooth de algum outro PC. Depois vais ao "Device Manager" e trocar os drivers por aqueles que copiaste. Ou então se o sistema te pedir os drivers quando encontrar o dongle, apontas para a pasta para onde copiaste os ficheiros.