A couple quick suggestions, should it indeed be a search engine:
1) Your web server's access log should log information about the requests, including the user agent. Google's hits will show up like:
Code:
::ffff:66.249.65.104 blog.hoopycat.com - [04/Oct/2009:23:36:59 +0000] "GET /tag/arduino HTTP/1.1" 200 5588 "-" "Mozilla/5.0 (compatible; Googlebot/2.1; +http://www.google.com/bot.html)"
This will at least help you identify what you're up against.
2) If it is a search engine, odds are good it doesn't need to be using your search function to find things. Notching it out via robots.txt may get it to go away and stop killing your search function.
3) You have memcached running, so might as well use that to track individual IPs

It doesn't have to work 100%, it just has to work well enough to calm things down, right?
Checking the logs is #1, of course... without knowing exactly what's going on, it's difficult to decide where to go. -rt