I also wonder what happens if you want to grant access to your VM to additional public keys and one of those public keys happen to already be routed to a different VM on the same IP.

Github has a similar system and just refuses to let you addthe key if it already exists. It's hacky but it's also obviously massively widespread.