If there is a demand for it, I might be tempted to start a webservice like the faucet where people can buy vanity addresses for a small bitcoin fee. I have a simple handshake scheme which allows me to generate a new address for you without me finding out your private key. My method sounds like it's faster than Gavin's and mathematically it's non-trivial. It can find addresses containing a short string like "gavin" in a fraction of a second for example.
ByteCoin
I think the claim that you can do this search without knowing the private key is surprising and dubious.
I'd be interested in hearing more about how you propose to do this.