Can one safely buy vanity addresses from a third party without risking one's coins from being stolen? One can easily generate vanity addresses for Bitcoin, but they can take quite awhile to generate. Outsourcing that process to someone with a strong mining rig is an option, but then one runs into the risk of the person generating the address using it without our knowledge to steal our coins. Is it possible to generate vanity addresses in such a manner so as to make it impossible for anyone to steal your private keys?
From what it appears, yes, it is possible, and quite simple really to outsource vanity address creation to a third party without risking anything.

Bitcoin addresses are created from ECDSA keypairs. Their property is that if you take two private keys and add them together (with appropriate modulo operations), the sum will map to a public key that is the same one as one would obtain by adding the two public keys corresponding to the private keys.

This means that in order to outsource vanity key generation, one can create an ECDSA keypair, store the private key safely, and give out the public key to other people. They would then proceed to generate ECDSA keypairs, summing the generated public keys to the one provided by you, and checking whether they map to the appropriate vanity address. If it does, they need only to give you the appropriate private key, which you then need to add to your secret private key in order to obtain the private key that maps itself to the vanity address.

JoelKatz explained it in his post, and I went ahead and implemented a "vanity pool" that enables such outsourcing. Moreover, I also created a simple testing suite for playing with combining the ECDSA keypairs. Currently there are no "split key vanity miners" available, nor any offline solutions for this problem, but they can follow shortly.