This is where the Client Subnet edns extensions come in handy. This allows the DNS provider to pass along the /24 the users IP address is in.

With an extra caching key, this can even be cached.

See https://developers.google.com/speed/public-dns/docs/ecs