This problem can be solved as follows: third parties who will provide public keys for generating a large number of vanity addresses should work according to some rules, for example:
1. function "get public key" - always returns a new public key to generate a large number of vanity addresses;
2. function "get private key" - based on a public key from function 1 the private key is given out. You can request a private key ONLY 1 time, then the public key is considered inactive and can not be used. When you repeatedly request the same private key, the service should give an error and say that the key has already been issued (compromised).


The service for generating vanity addresses will work according to the following algorithm: a request for a public key from a third party, a private key, it will not be requested, because the private key will then be compromised. Next, the service looks for many vanity addresses, if found, then sends the customer a vanity address and a third-party public key. And when the customer wants to get a private key from a third party, he will already know whether the key is compromised or not. And then the algorithm repeats.