Phone Book Lookup Query

Hi,
Can you recommend the best way (fast and most productive) to search an
employees table?

Let's say I have a table that has this kind of structure:
firstname, lastname, state, city, street, phonenumber,
socialsecuritynumber, dateofbirth, etc.

I'd like to provide a search window with one text entry field, that
the text entered will be searched at all fields, and even in more then
one field toghether (like if you enter "david z" it will search for
like '%david%' in first name and like '%z%' in last name).

the problem is I can't write the query that'll perform fast but search
all of these fields, plus there's no way to use an index when using
LIKE.

I can't loose the functionality described above (I'm not the client,
and not the project manager) but I am trying to find an efficient
solution to the problem.

Since most systems has some sort of directory table (like authors in
pubs) you would think it will be a classic problem, but I found no
recommendations on how to approach it.

any help will be most appreiciated.