I recently went through the list above and a few that I regularly use and can confirm that the following are working (as of yesterday). The sites do change their search parameters as well as some are no longer available:

http://answers.yahoo.com/rss/searchq?p=KEYWORD
http://api.search.yahoo.com/ImageSearchService/rss/imageSearch.xml?appid=yahoosearchimagerss&query=KEYWORD&adult_ok=1
http://api.search.yahoo.com/WebSearchService/rss/webSearch.xml?appid=yahoosearchwebrss&query=KEYWORD
http://blogdigger.com/search?sortby=date&type=rss&q=keyword
http://bloglines.com/search?q=keyword&ql=en&s=f&pop=l&news=m&format=rss
http://blogsearch.google.com/blogsearch_feeds?hl=en&q=keyword&ie=utf-8&num=10&output=rss
http://feedplex.com/rss-search.xml?q=keyword
http://feeds.technorati.com/feed/posts/tag/KEYWORD
http://feedsfarm.com/s/keyword&format=rss
http://findarticles.com/p/search?qf=all&tb=art&x=21&y=12&pi=rss&qt=KEYWORD
http://flickr.com/services/feeds/photos_public.gne?format=rss_200&tags=KEYWORD
http://fybersearch.com/rss-search.xml?q=keyword
http://goarticles.com/cgi-bin/rss-search.cgi?search_content=KEYWORD&l=20&s=1&c=none&D1=advanced
http://icerocket.com/search?tab=blog&q=KEYWORD&rss=1
http://icerocket.com/search?tab=news&q=KEYWORD&rss=1
http://icerocket.com/search?tab=web&rss=1&q=KEYWORD
http://news.google.com/news?hl=en&ned=us&q=keyword&ie=UTF-8&output=rss
http://news.search.yahoo.com/news/rss?p=keyword&sm=Yahoo%21+Search&toggle=1&cop=&ei=UTF-8&eo=UTF-8
http://podscope.com/rsssearch.php?s=d&assetID=&q=KEYWORD
http://search.msn.com/news/results.aspx?q=KEYWORD&format=rss&FORM=RSNR
http://search.msn.com/results.aspx?format=rss&FORM=RSRE&q=keyword
http://sphere.com/rss?q=KEYWORD&datedrop=1&lang=en&x=0&y=0
http://video.google.com/videofeed?type=search&num=20&output=rss&q=KEYWORD
http://www.plazoo.com/en/rss2/keyword.rss?s=dt&fc=&currRPP=10&currEF=64
http://www.topix.net/rss/search/article?q=keyword
http://youtube.com/rss/tag/KEYWORD.rss
http://www.blogpulse.com/rss?query=keyword&sort=date&operator=
http://www.goarticles.com/cgi-bin/rss-search.cgi?term=keyword&&l=20&s=1&c=none&D1=subject
http://www.feed24.com/search.xml/keyword?mode=date
http://www.connotea.org/rss/tag/KEYWORD

If you are using an RSS rewriter script some of the above won't properly work. Test each url with your replacement keyword before relying on them.