As you know Google Site Search is going away shortly and will be replaced by their ad supported search...not much use for a commercial website! I have been looking at Addsearch, but their integration isn't the best (wordpress plugin is currently unavailable and their recommendations don't actually relate to Wordpress). Although I seem to have a work around, it would be great if this plugin allowed for other types of search integration, not just Googles.
Ones I have looked at include Amazons, Solr, however in the case of this site neither of these worked well. Addsearch seems a reasonable cost solution.