Assuming you can access the UI of the Cloud Key, what then? How do you actually add it back to the unifi.ubnt.com side of things?

Lets assume the unifi key is located on the LAN.
Going there with a browser prensents you with a choice of either „Manage your devices with Unifi Controller“ 

Click Manage. That brings up the Controller.

Then go to Settings > Remote Access. Disable and re-enable it.