SSH key was deleted without audit log; unable to add ssh key again

We just deleted 3 SSH keys from a developer that left our company. I then renamed our jenkins key to "jenkins-old". After that it was not listed in the SSH keys. I tried logging out and back in, and also fully reloading the web page. It is still gone.

To make matters worse, I cannot add this SSH key again, I get the error "Someone has already registered that SSH key."

However, the pubkey still continues to work. So currently we have a SSH key that can access our repos that is not listed under SSH keys, and can't be removed anymore. The pubkey in question is:

#!bash
ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQC3Kc1YrckO1iDt+c99u6ICP9ip0paqnoYQm8J+vNyWdq8nnZ16yvNFTIiNM7e3jPoxQOLSXpZET0emQ4weLnp/fPBqjYS7HiDcSyyTWB7EI+J2e6LWjtltwIseLMiySMiVFSjSkl45U1d0M3WN3SOssyzMCgmNQwYia/+xx2ZC5AyTRztck8iri5fy6B391EU4KhsSUw/7A45i+UODj8E2clKcDZySlII6hByVzavkz5ndr/PEE9xZCRgKofZeM6CiUZj2aUS5+rbsorjkAd1jkCPj46oP20PwizoMIpKYNhVQrjRrw7DyJ4gujpO6T+qU1RB/aVIyvPyU3QUfHVst jenkins@ip-172-31-16-82