I have implemented Google Custom Search on enstage.opensuse.org, and I am personally very happy with the results. To try it out, you can visit http://enstage.opensuse.org/Portal:GoogleSearch and try searching on anything you want. It is about a thousand times better than what we have, and with the better relevance ranking, namespace searching is no longer an issue.
While the current search is advertisement supported, I am nearly positive that we can get ad support removed. It seems that Google is pretty willing to do this for non-profits.
What does everyone think? If you don't have access to the staging site, I will be more than happy to send you a screen shot of the search page.
If everyone is on board, I will ask Thomas to edit the theme to make it the default search, and we'll send it live.
Thanks,
Matt