We need a better search function on our closed membership site - but plugins create trouble

Hi there

I am running the premium membership plugin on a P2 theme (both up to date) and experience this:

When running normal search, the users can see search results - and visitors cannot. Good!
But wordpress search is terrible - no sorting by relevancy, no search in comments etc.

So we tried two of the popular plugins that improve the search function in wordpress, but:

When activating the 'Relevanssi' or 'yolink Search for WordPress' only we two admins can see search results. All the users just get a message of no posts found when they use the search function.

The Relevanssi plugin can not be used with Membership Plugin at all - It turns out non logged in visitors can find all the hidden content via the search function when that plugin is installed!

With yolink that does not happen, but still the _logged in users_ find nothing when searching with that plugin active

What should we do?
We do not care what plugin we use - as long as we can get som better search results for our logged in users.