Give it a try and see what happens.
People said greylisting against email spam wouldn't work, since spammers would just resend. It works since 20 years. To get your IP off the DNSBL NiX Spam you just have to follow a link. People said spammers would automate that process. Never happened in 19 years. Sometimes spammers are just lazy.
Newest captcha services are a prediction score, not even a verification screen, and you can feed polluting data to bots you are certain to exist.
For OP, I think simply not returning results at all is a more practical measure because it removes the reward completely. Captchas and bot detection keep the reward in play, while taking away the results entirely makes the entire pursuit futile.
If anything, it might be best to return a page that explicitly states "Sorry, this search engine no longer supports SEO footprint search queries."
*edit for typo & wording