I signed up for Google's APIs around 2002 and used it until they stopped the service. I later switched to Microsoft's Bing APIs: the cost was great, free! Bing's new entry level cost of $40/month for 20,000 queries does not match my use case. I wish they had a $5/month for 2000 queries.
I do a low volume of search for personal research projects and prototypes. Yahoo BOSS's service has an attractive price but I worry about the service being terminated with the deal with Microsoft. Google offers custom site search, but I didn't see any options for a general paid-for web search API.
So, I signed up with Yahoo BOSS for search and if the service is ever terminated, I will look elsewhere. The price is good, $0.80 per 1000 queries.
2012-05-19 edit: Bing search now has a free tier for up to 5000 search requests per month. Cool! For research purposes, this is good enough.