>
> use bluez-utils-2.17 and use a clean start. Don't modify hcid.conf and
> remove the link_key file (new place and file format since 2.16). Run
> "hcidump -X -V" to show what happens.
>
> Maybe your headset is broken.
>

I think that the headset is not broken rather than the dongle. 
I tried to pair the headset multiple times with my new thinkpad that has a 
builtin bluetooth device an it works without any problems. 
After that I also tried it with the bluetooth dongle on the thinkpad and it 
doesn't work. As they are both using the same module 'hci_usb'
I assume that it must be the dongle that is causing problems.

Maybe this dongle does not work like other dongles and is not fully or proper 
implemented in hci_usb driver. 
The dongle is a "Allnet ALL1575" Poor product infos are available on 
http://www.allnet.de/product_info_allnet.php?cPath=_&products_id=22844
I'v attech the output of lsusb -vvv maybe that helps to track down the 
problem.

Regards 

Ruben