Into the client certificate's DN or extended field they write the allocated public IP.
The only information they need to store is that that IP is spoken for and not to be allocated again. They could also work this out on the fly.
When the client comes to connect, they note that the certificate is signed and presented, and they route the public IP to the in-tunnel address of the peer, which they will have standardized to something meaningless like 10.0.0.2
As long as they don't log anywhere in the process, the signing of certificates means you don't have to remember the client at all.