I don't have that phone, I have an HTC HD2 that I've tried dozens of hacked versions of Android on. It currently thinks it's a Nexus running ICS (Android 4.0.4). I have had very few problems re-pairing these with the HU.
Your problem may be the way you are doing it.
I always set the phone to the BT settings, then go to the HU: Settings/Bluetooth Settings/Registration/Registration from mobile phone.
Then you get a dialog box saying something about following the instructions on your phone.
On the phone, make sure you scan/search for devices. Soon the HU should show-up (I always change the BT registration names for HU & phone, so I know for sure what I'm pairing with). Select it. Enter your pin (you do have a pin set on the HU?), and it just works. Very rarely, I have to try twice - but it always worked.
The HU will then try to download contacts from the phone. The phone needs to accept this DL request - so there will be some sort of dialog- or maybe an icon on your phone's status bar that you need to open.
BTW, I have found that some things like streaming audio and auto re-connect work better (reliable) on some Android distributions. ICS seems be the best I've tried so far. But this has noting to do with pairing. It is in the transfer of streaming audio from phone speaker or BT headset to the HU.