There have been many proven approaches how to solve this.

For example "blessing" the enrollment of a device using another one, potentially across physical locations (i.e. similar to what discord and steam did at least for a time as far as I remember).

> How would you sign up a new service under this scheme?

the same way you do now, there is no difference