They just need to set the limit on the number of VMs per user to be less than or equal to the number of public IPs they have available. As long as two users don't try to share a key, you are good... which should be easy, just don't let them upload a key that another user has already uploaded.