IPs that you've never seen before are hitting a single random page deep within your site are bots, or first-time followers of a search engine link. Grey list them and respond slowly. If they are seen again at normal human rates, unthrottle them.

Aka, make the web worse for everyone. Thanks for playing.