I had minor issues in the past with bluetooth pairing. I have a sony-ericsson HB30 bluetooth car-kit and regular mobile phones paired perfect and stayed connected.
My windows mobile devices also worked fine, only sometimes difficult to connect from the first time.
My blackberry curve connects perfect, no trouble at all. I get message when connected and working like it should.