Evaluating a search engine

I work for a medical association, and we maintain a member website with its own search function (not Google).

The problem is our search is pretty lousy and pulls up a lot of results that may or may not be what our user base is looking for. We worry though that if we do user testing and give them specific search terms, that we will not get to the heart of whether these results are relevant to the user, because they won't really care about the term they're looking up.

How do you test whether a search engine is meeting the needs of a specific user base, while still getting somewhat organic results? Our thought is that we ask the user to come up with their own terms, search, and evaluate the results they get back. But is that too taxing? And what if they only pull up results that don't illustrate the problem? Any feedback would be helpful. Thanks!