It would really help to know what database you are using.
At the company that I was working at, until I was laid-off :( , we were using an Oracle database and we were dealing with public records. I remember when we were designing a website we were having problems with the performace of doing a search on smith. We ended up using function based indexes and limiting the number of records that were returned. First we ran all of our names through a program that would CASS certify them. Then we used a function called stripstring() which would remove all spaces,', and - and upper case the new string. Then we would index that value using a function based index. When the end user entered the name John Smith we would convert that to JOHNSMITH and then use that value to query the database. We also limited the search to 200 records and it only took a few seconds to return the results. I hope this helps.

Sam