I've been out of touch with the whole web thing for way too long, so I spent a few hours over the last week hacking together a web app that aggregates data from every search/tagging API I could get my hands on, namely Google, MSN, Technorati and Amazon. And it was FUN. They work well enough for late night hacking and were a cinch to use, although they are all offered under beta or recreational licenses at the moment. None took me more than 15 minutes to get working, less time than it took me to learn ASP.NET to display the results. Here's my service scorecard, where I have praised and lambasted based on discoverability and ease of use (are the types and operations intuitive? did I have to read the documentation?); features (what types of search do they offer?); speed and reliability. As I said, I only glanced at the APIs and ran a handful of queries, so caveat lector.

MSN
Discoverability / Ease of use: SOAP. I created a proxy using Visual Studio and the generated code was neat: MSNSearchService.Search(_) does the trick.
Features: Plenty of query types - I used "web", which is a vanilla web search. Also supports news, ads, phonebook, spelling and something called WordBreaker. Location capability is cool.
Speed and Reliability: Ten results costs me ~3 seconds, and all my queries returned something.

Google Search
Discoverability / Ease of use: SOAP. I created a proxy in Visual Studio and the generated GoogleSearchService.doGoogleSearch is pretty easy to locate. Working out what message parts lr, oe and ie do is trickier, and not explained in the WSDL. One mark off for making me read the documentation.
Features: And another mark off for only allowing 10 search keywords. Otherwise great - search is simple, and spelling and cache gets are also exposed.
Speed and Reliability: Ten results in ~4 seconds, but some periodic "Bad Gateway" errors.

Amazon E-Commerce Services
Discoverability / Ease of use: SOAP. Again, I created a proxy in VS. The generated code was not pretty: Accessing a search result via Items.Item[_].Item annoys.
Features: A Swiss army knife of an API, it looks like it does everything imaginable. The bulk query capability makes great sense for enabling serious applications (no way I forgive that Items palaver though). Results were patchy though: A lot of my admittedly obscure queries yielded nothing (no books on Lakshmi Mittal?). Not sure if there is some ANDing / ORing needed.
Speed and Reliability: Fast and reliable. Responses in a couple of seconds tops.

Technorati Tag Search
Discoverability / Ease of use: REST. Result XML format is sensibly named, easy to grok. Coding a WebRequest and parser takes ~5 minutes (vs. 0 minutes for a SOAP service), but from that point it is plain sailing.
Features: What features? Absolutely basic, which works perfectly for me. Can return results as XML or RSS. Optionally serves up parent blog information along with results. I think the lack of a bulk capability would begin to hurt after a while though.
Speed: Slow and variable - ~4 seconds and up to 8, sometimes timing out.

In summary: Awesome fun to play with. Some kinks. The future.