I would guess your chances of finding a MultiSig vanity address would be less that hitting a national lottery...
- snip -
For a MultiSig, you need to find at least 2 private keys (for a 2of2 setup... basically you need M private keys in an N-oF-M MultiSig setup)... that when combined will generate a redeem script that when hashed will convert to the desired vanity address.
The chances of being able to do this are somewhere between slim and none
This is not true. Depending on what you want, generating a multi-sig vanity address is either the same difficulty and effort as generating a "normal vanity" address, or possibly faster and easier.
If you are trying to create a 2-of-2 address, you only need to search for one new key, that when added to one unchanging key results in the address you want.
In otherwords, it is exactly the same amount of work as needed when searching for a "normal vanity" address.
Furthermore, if you just want a vanity address that starts with a 3 (instead of a 1), then you don't need to use multi-sig. You can use a P2SH address that uses a single key and a nonce.
If you are willing to have a nonce in your script then, regardless of whether you use milti-sig or not, you only need to generate the private key(s), public key(s), and signature requirement part of the script once. After that you just increment the nonce, hash the "P2PK + nonce", and compute the address from the hash. This would be less work and faster than generating a "normal vanity" address. It also could be done by a third party completely securely without them needing any private key or private key component from you at all.
