That is a great story, at Blekko my first attempt at getting rid of people trying to exploit the index was to ban any address that did more than 100 queries per second, that got a bunch. Then they start showing up again, at 99 queries per second :-). So I lower it to 50, same pattern but now 49 qps, then set it to 10 qps, they would limbo in under the wire again. They would also start using bot nets to send their query from different PCs in different places (all the same query though, typically looking for ecommerce or wordpress templates with known exploits) We would nail them by finding all the machines that made the same query, then we could just start killing any query that asked for more than page 10 of the results, etc.
For a while I pondered if I could use my ability to change their behavior by changing my rules, to get them to actually create a set of behaviors that would unmask their C&C servers but not enough free time for that.