I went through a hassle I thought I'd share with you all here, in the event I can save someone doing the same stupid thing I just did.
I have a Samsung Focus i917 hooked up working fine with my Car Audio and Phone. Then I bought a Nokia Lumina 710 and hooked IT up and everything worked fine. Now I'm selling the Samsung, so I decided to delete the Samsung from my radio. Bad mistake, I guess. Next time I came to the car, neither device would pair.
So, I searched online and everyone said re-format the phone. Since I had the Samsung already formatted, I tried reformatting that and it worked. So, UNFORTUNATELY, I reformatted the new Nokia. It did work, but now I have to set up everything all over again.
So, while I was trying to pair the reformatted Nokia, I FINALLY read the pop-up message. And it said "If you ever want to re-pair with your other Device, just delete this device, and re-pair." They don't mention how, but I tried press and hold, and delete was an option.
DAMN! Why oh why don't I read? And Why is it never obvious with Windows? (Both phones are Windows Mango and neither phone has any options other than "searching".)
Another nightmare was with Zune. I kept removing my phone from Live and Skydrive, and it kept popping back up and sending me welcome emails. Finally a search yielded, get rid of the phone in Zune. Again, Microsoft, why don't you say that in Live & Skydrive? Why are there 3 places?
Rant off. Just a warning for anyone else trying to pair bluetooth to their car. Probably obvious to most of you reading this, but I was not able to find the answer searching the web.