The site when originally developed started with MSSQL7, and has since migrated to MSSQL2K. While I wasn't too impressed with early incarnations of the product, I do have to admit that it's getting better. Would still love to try on Oracle sometime. . . but I digress.
Following one suggestion, we tweaked the indexes on the master name table. We have been able to squeeze some more performance out of the initial name search, and are starting to look at the rest of your suggestions on how to best cache and redisplay the results of user queries.
Currently, the data set grows once a week by several thousand names, but will likely be updated on a daily basis in the not-so-distant future. Being more forward-thinking this time, we're going to plan for daily updates NOW so something like this doesn't bite us in the rear again ;)
Thank you all for the time and effort of responding to this. If my little bit of additional information adds to/changes any suggestions, I'd love to hear those as well.
Respectfully (and thankfully!) yours,