I have some Nokia HS-12W bluetooth headphones and to be honest I am disappointed with the results which I suspect has more to do with the phone than the headset.
I find that if I am more than about a metre away from the phone or the phone's memory is in anyway dealing with any other task, that I get constant skipping. I have come to the conclusion that this is because the phone memory can't keep up with the streaming but that is just a guess.
Also, I have found that the radio reception is a bit poor so quite often I get a lot of static noise, even on the strong stations. Sometimes it's okay though.
It is possible that either my headset or my phone are in some way faulty because I have read other peoples posts regarding the HS-12W and they have had some good results. Perhaps I am just unlucky
I have resorted to going back to using the standard headphones and using streaming radio instead (I am on T-Mobile so doesn't cost silly amounts of money for the data use).