Many users on the same IP, IP is registered to a cloud hosting company, etc. They'll never have perfect detection but you can do pretty well without much effort.
So they're either reading signatures left on the packets by various VPN / proxy technologies (fragmentation and other obscure metrics), or they're blocking the IP ranges of major hosting providers, or both.