What's the best way to deal with soft 404 errors from Google? I have hundreds of soft 404s which are empty search result pages. I don't really want to have to manually create url rewrites for all of them.
I think you should ask yourself why google is crawling this much dead ends on your site in the first place. There should be links to these pages on your site or you have disappearing content. Disappearing or moving content should be redirected using 301, 302. Dead links aren't good either. Your Google webmaster tools will tell you if you have it setup. I recommend doing so.
Magento's default search functionality isn't very helpful. I always recommend a search plugin to my clients. There are many available in different price classes. I especially like the one from Mirasvit as it frequently gives good results. It's also able to redirect straight to a product or CMS page if there's just one (obvious) match from this search.
Another option would be to redirect all 404's to home using 301's. There's even an free extension available for this on Magento Connect