There are about 60k ports you can choose from for each IP, so I don’t understand why you can’t just give one user 1.2.3.4:1001 and the other 1.2.3.4:1002 and route that.
Setting it up like this where you just assume:
> The public key tells us the user, and the {user, IP} tuple uniquely identifies the VM they are connecting to.
Seems like begging for future architectural problems.
Something like getting SSH to support SRV records would allow that to be transparent to the user: https://github.com/Crosse/sshsrv