WhitePages.com allows you to search for people and businesses on the web. They even provide a Developer API which you can use to provide search on your website.
I thought of registering there and going through it and show any one who might be facing problems on how its done.
You can view how it works by going here