Does a Vanity Address reduce the randomness / entropy of the private key? Is there cryptographic proof? Since a vanity address discards many "valid" keys in order to find one that matches a pre-determined string, I think that the "randomness" of the data would be reduced, thus weakening the key.

Is there any cryptographic proof that indicates how this is / is not a factor in reducing the security of a given address &amp; private key combination? 

... or at the very least calculate the degree of "lost randomness"?
Vanity Addresses only reduce the apparent randomness of a public key. The underlying private key is still just as random as always, as the private key does not have any special characteristics (it does not have a special pattern in front or anything like that). A given public key is as likely to be generated by a private key from range 0-10, as for 1000000-1000010 and the like.

If knowing some given pattern would make it more likely that one would be able to find the private key, then since every public key is known when coins are spent then vanity address or not, it would be just as easy to steal one's coins.