You could also hook into tags_start and make it so that users who are not logged in can not see the page, that would stop the bots from executing the search queries.
Never thought of that. Good idea. I think I will write something up for it and see if it works.
EDIT: Although this would stop them accessing the tags page, it would not stop them from requesting the page.