Maybe just try a different CAPTCHA system and see if they can break it?
Heard about this one recently:
http://recaptcha.net/
And, like how GIMPS puts spare CPU cycles to good use, this puts spare CAPTCHA readings to good use, helping computers do OCR on books to digitize them.
Also/instead of my above suggestion, maybe you can make it put a temporary, automatic lock on anonymous searching when a flood of searches is detected, even from different IPs.