Finally Google has listened: The new Google Enterprise: Google Custom Search Business Edition offering (starting at $100 per year for 5000 documents or less) can now be configured NOT to show any ads on the search results page. So now you can use this service and offer a site search on your site without the risk of your visitors being distracted from your site by Google Ads.
Quote: “The Business Edition turns off ads and allows you to access search results through an XML API. This means that you can create your own user interface for search results and have your search engine fit in seamlessly with the rest of your website. Custom Search Business Edition starts at $100 per year for searching less than 5,000 web pages. “
Here is a Comparison Matrix of the free and the new paid-for service.