What you could certainly do is tell your users that "Hey, we have a large DB. If your search returns more than 50 results, you only get the first 50!".
Then, tag on " LIMIT 50" to your SQL query. Now, if you persist on storing those 50 results somewhere, you might even try sessions/cookies/etc. Sessions wouldn't be too hard... just cram all the results into an array or two. Not sure if this is very efficient.. someone else will have to chime in on that.
With as many records as you say you have, I would most definitely use "WHERE firstname='$search_firstname'" etc, and then at the end a "LIMIT 50". Then, if they wanted to look at the next 50... make up a system that 'chunks' the results, so-to-speak, i.e. "LIMIT $currpage, $currpage+50".