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.
How does this work? You HAVE to explain it or the public wont trust your keys.
At the moment addresses are used as fairly ephemeral things and the recommendation is to use a new receiving address for each payment. This limits the utility of vanity addresses and so I don't believe it's worth implementing. This may change in future however as new bitcoin services arise.
It can be implemented securely but the method touches on some issues I should currently keep confidential. However it's an elementary problem for any half-way decent cryptographer.
ByteCoin