Just a few thoughts on new features for WPSearch:
1. Option to include comments in the search results.
2. Option to exclude certain pages or posts from search results.
3. Stats on search phrases, number of successful searches and number of failed searches.
4. Highlighting of search phrase in search results - different background color or bold text.
5. Option to limit total number of search results (idea is to add further relevancy to results).
6. Option to limit search results based on a match score visible only to the admin (see Yet Another Related Posts Plugin).
I think 1 and 2 would add tremendous value right away in terms of added search relevance.
Search stats (3) on what's not being found would be a great tool for generating new ideas for content.
Search phrase highlighting (4) is a nice to have but not critical in any way.
Limiting total number of search results (5) and limiting search results according to a match score threshold (6) would provide additional control over search relevance.