My first assumption is that Bitcoin uses the standard public/private key infrastructure (PKI) - the same one used for SSL - because that is what I am familiar with.  However, since I have never actually read up on it this is just an assumption on my part.  Given that Bitcoin uses the same public/private keypair infrastructure as SSL then the paramters are all defined as follows:

p  = first very large random prime number
q  = second very large random prime number
n  = pq (also a very large number)
m = lcm {p−1, q−1} (lcm is the least common multiple)
r  = is a selected coprime with m (r>1 and r and m have no factors in common), most commonly set to 0x10001 = 65537
s  = the unique s such that rs ≡ 1 (mod m)

The public key is made up of n and r

The private key is made up of n, r, p, q and s (m and n can be calculated from p and q - see above, and all you really need is n and s to decrypt - see below)

Encryption of message M is defined as Encrypt(M) = Mc = (M ^ r) (mod n)

Decryption of the encrypted message Mc is defined as Decrypt(Mc) = M = (Mc ^ s) (mod n)

I thought this was pretty standard terminology but I found that http://en.wikipedia.org/wiki/RSA_(algorithm) has it slightly different:

p, q, n are the same.  They have φ(n) where I have m, e where I have r, and d where I have s.

I have updated this post and fixed all the glaring/embarrassing mistakes I made.  Please let me know if you see any others.  Keeping in mind this is all finite field mathematics on an elliptical curve - which is "hard” - I think the algebra is pretty simple and may now even be correct:

Using G as the base point on the curve and p as the private key then the public key P is defined as simply P = pG.  Therefore, the algorithm is as simple as BTCurious says:

Person 1 hands out a public key and a vanity request (or list of vanity requests) to the "vanity address miners"

The vanity address miners do the following:

1) Generate a random test private key from the finite field, let’s call it t.
2) Calculate the corresponding public key but instead of calculating it from the base point G calculate it from Person 1's public key, simple:  T = tP
3) Hash and check the generated public key T against the vanity criteria, if it does not match any of them then go to step 1) if it matches one then continue to step 4)
4) Transmit the private key found (t) back to person 1 [t could be easily encrypted using P]
5) Person 1 can then calculate the vanity private key from the private key sent by the miner (t) and the private key they originally generated (p) as follows:  P = pG, V = tP so V = t(pG) and V = (tp)G so the vanity private key is t times p.
6) Then the corresponding key V = (tp)G = vG is the vanity public key!
7) Person 1 can simply hash and double check the public key found (V) and then pay person 2 for their help.

This is VERY COOL, very simple and will work as far as I can tell.

This is impossible. The public keys aren't neatly ordered in line, so you can't calculate the private key difference between any two public keys. The problem is that it's impossible to know anything about the private key, given that there's only the public key…

Edit: If this was possible, I would just generate a private P_M, get the public key M, and then get person 1's private key by calculating P_M - m1 = P1

You are correct in that my post was totally incorrect and that my idea will not work.  But, in my defense, as a side note, point addition and point subtraction are defined for the elliptical curve group.  Unfortunately it turns out that I actually need point multiplication/division to be able to get the idea to work and those operations are not defined.

Yup, your edit for the process (between two people) is correct now.

One small addition: An alternative to multiplying the two private keys, you could also make a scheme where you would add the two private keys. In my imagination, adding of bignums is easier than multiplying. In practice, you're using a bignum library (or python) anyway, so it doesn't really matter.

For completeness, here's the script with adding of private keys, instead of multiplying:
So yeah

Anyway
Well, there's the trivial solution of just having N people, and then when person x's address is found, asking the other N-x people for their private keys.* Ideally you don't want to contact the other N-x people at all, but this seems impossible.

Imagine this was possible. Then, when a vanity address was found, I (as a host, or the person searching for addresses) would give all the information I have to the relevant customer. The customer would then calculate the vanity's privkey.
If this is possible, then I (as a malicious host (remember, we want a scheme where no one has to trust me)) can also act as a customer to my own service, I can duplicate the information I send to the vanity customer, send it to myself as a (fake) customer, and also calculate the private address.

The only way this could be made to work, is if somehow the vanityness of the address was involved, meaning the resulting private key could only be calculated by the person who actually submitted the vanity request. I wouldn't quite know how to do this. But then still, I could pretend to submit a shorter vanity address for every vanity address my customers submit.

So I think this scheme is impossible.

*The "trivial solution" is very possible, and may not be a bad idea. It just requires some coordination, and it requires people to leave their tool running. The tool could either be a program that does nothing, except respond to a getPrivateKey request from the rest, every now and then, or it could be an active searcher, helping in the search for the vanity addresses^¶. A proof of work principle could be employed, similar to coin mining°, to give these active searchers a share of the fees for the vanity address.
Ideally this could be done nearly identical to p2pool, but I know nothing of p2pool, so screw that, and just put in a "host", through which all communication is conducted. One problem is offline node detection though: When someone exits their program, everyone needs to start calculating from a new sum-public-point, which does not include that offline node's private key anymore.

°Imagine sending in every time you find an address that starts with 1111111, and its corresponding private key. The host would have to keep a list of seen 1111111 addresses though, to prevent cheating. Not ideal… may require more consideration. Alternatively, just pay the full fee to the person who found the vanity address. This is easier, but makes the payout more lottery-like. When there's lots of vanity requests, this doesn't matter.

^¶If these searchers have no requests, then they don't need to add their public point to the sum-public-point. This helps, because you also don't need to detect it going offline, he can stop whenever he wants.

Yeah, that's roughly what I meant, however, when one of the "everyone" is suddenly disconnected, then point 5 can't be done anymore. So, as soon as there's a disconnection, all users need to generate the new common public key. But then you need to detect someone disconnecting, somehow.

As far as I can tell, the only thing the transaction script would have to do is convert the actual public key (Pub2) into a Bitcoin address.
The transaction script can do that using OP_HASH160 as far as I can tell.
Assuming the vanity address only needs to match a certain prefix, ie. the start of the address matches "xxx", then a simple binary AND operation should be able to tell if the first x bits in the address matches the pattern that is specified in the original vanity address generation request transaction.
If we want to be able to find vanity addresses that match patterns in any position in the address, it would be a bit more complex, but still doable I think. Matching multiple patterns, or even a Regular Expression is a lot harder, but since using a reg ex slows down oclvanitygen considerably anyway, this probably isn't a going to be fulfilled, unless it's very simple. And if it is very simple, multiple, simpler transactions could be made instead.

Yes the reward that would go to whomever finds the valid address is locked until someone finds it. I haven't been able to find out whether it's possible to create a transaction that "times out" after a certain period, so that the reward is not lost in case no one can or wants to find the vanity pattern specified in the transaction.

Regarding telling people that I have a vanity address that they should search for; the Bitcoin network will propagate the vanity address generation transaction (VAGT from now on) to all nodes (like it will with all other transactions), and a special Bitcoin client will need to be run that can detect these special transactions and present them to a user who wishes to use compute power to try to find vanity addresses in exchange for Bitcoins. This client would leverage the technology of the original Bitcoin client (connecting to peers to get transactions, downloading the block chain etc.) but would only look for VAGTs and present them to the user:
This special client would then run oclvanitygen, oclvanitygen would run until the pattern is found and report the Priv2,Pub2 key-pair to the client, which would then create a transaction in the network that spends the reward by providing the Pub2 that, when converted into a Bitcoin address, matches the pre-defined pattern that was in the VAGT.
A website could easily be made where the back-end is this special client, and any user can go to the website, type in her desired vanity address pattern, deposit x Bitcoins and the website back-end creates the aforementioned transaction on the network and returns the result to the website user, when or if it receives one.

Regarding ByteCoin's proposal: why would we need to coordinate anything? Can't each worker just start at a random point, and the probability that two will work on the same keys will be extremely small?

^ I blatantly admit to knowing very little about EC cryptography, so I was going off BTCurious' explanation which I took to mean that the search for a vanity address can be offloaded entirely to a untrusted third party, and the result needed to generate the private key for the vanity address can be made public without revealing the resulting private key.

Now I apparently didn't read the second paragraph very well, but if this means that an exchange must take place after each unsuccessful generation of a private/public key pair in search for a vanity address, it will obviously make this method unfeasible.

First, I like the "adding keys" solution better than my "muliplying keys" solution so I suggest we go that route.

It seems to me there is a workable solution here all we need to do is solve a few logistical issues!  Fun.  Going off line is kind of a nasty issue in that from the time one participant goes off line to the time this is detected and the common starting point is recalculated the efforts of the entire network of participants is wasted.  I think there are two separate "going off line" use cases.

1) a participant decides to shut down for whatever reason - in this case an "I am going to stop participating" message could be broadcast.
2) a participant goes offline without a message (power failure, etc.) - in this case we want a mechanism to detect this as soon as possible and get back on track

In a peer-to-peer implementation could't we have each node monitor just it's connected nodes and then broadcast a "node X went offline" to the entire network as soon as it detects one of it's peers has gone offline?