I've been thinking about this for a bit, and mainly about the possibility of merge-mining many addresses at once, to massively increase efficiency. This is what I've come up with:
1. Everybody who wants an address generates an ECDSA keypair, a Personal Pair
2. Everybody gives their public keys to the pool, which combines them into the Combined Public Key
3. The pool distributes the Combined Public Key to miners. The miners generate random keypairs until they find the right address when combined with the Combined Public Key, the same way it's done with split mining.
4. The randomly generated private key is given to the person who requested the address
5. Everybody but the person who requested the address gives their private key to the person who requested it.
6. The person who requested the key can spend funds by combining the pool's random private key, everybody else's private key, and his own private key.
7. Everybody else generates new keypairs and mining starts again, return to step 1
There are issues (for example, what if somebody chooses not to give up their private key after someone else's address is found?), but perhaps it is possible to work around them. This could make a big difference for mining speed, and I'm sure it is worth the downsides.
EDIT: I'm not the first to come up with this, apparently. See
https://bitcointalksearch.org/topic/merge-mining-vanity-addresses-1715787 by user ArcCsch. When I am done with my current project, I may begin work on a merged-mining pool, and looking into cool aspects of this, for example the most optimised way to split up into smaller merged pools to minimize risk while still keeping profits higher than with "solo" mining.