You can delete a phone, I've done it many times.
Page 138-139 of the NAV manual.

Bring up the phone page.
Hit "Settings"
Hit "Bluetooth"
Hit "Delete"
Select the phone you want to delete.
Touch "Yes" (to confirm)

Also, I have had problems pairing my phone after rebuilding it. You are correct, the trick is to delete the existing registration first.

Hope this helps