Fundamentally it's adversarial, so expecting a single simple concept to properly cover even half of the problematic requests is unrealistic.
Specifically, I use fail2ban to count the 404s and ban the IP temporarily when certain threshold is exceeded in a given time frame. Every time I check fail2ban stats it has hundreds of IPs blocked.
You block all VPN users then, and currently many countries have some kind of censorship, please don't do that. I use a personal VPN for over 5 years and that's annoying.
I understand the other side and captcha/POW captchas/additional checks is okay. But give people a choice to be private/non-censorable.
Enabling/disabling a VPN each minute to access the non-censored local site which blocks datacenters IPs, then bringing it back again for the general surfing is a bit of a hell.
What I mean is that it's better to give VPN users the choice to solve captchas instead of being banned completely.