Well, at some point you have to block legitimate traffic. My thought was it doesn't have to be black and white. Maybe require the user to solve a captcha after the nth search from the same IP address? How big are the biggest of botnets? A few hundred thousand computers? Or maybe even require captcha for every unauthenticated search.