We confirmed with CA Support that it is expected behavior to have to use a two step removal process to delete a Primary Contact from a CI. (2. Contacts, location, organizations tab> 1. Contacts nested tab)
If you edit the record and change the primary contact to a new user, the original primary contact automatically drops down into the "Other Assigned Contacts" list. As an administrator, you may or may not notice that this individual that you removed as primary contact is still associated with the CI.
I propose that if this functionality to maintain the original contact as an other assigned contact is required, at the time of editing the Primary Contact field, you should be given the option to completely remove the individual from the CI or move them to the other assigned contacts area.
A two step deletion process for each CI that a person is affiliated with when they leave their job is not user friendly.