As it stands, you are correct, with some minor caveats...
When the Caching Server starts up (and periodically while it's running), it checks in with Apple, and Apple tracks the public IP address of your server.
When a client checks for updates, Apple cross-reference the client's IP address with the list of known caching servers. If it finds one it redirects the client to their local cache server.
Since this mechanism is transparent - there's no configuration or interaction on the user's part, the IP address has to match since there's no other way for Apple to know if the caching server is on the same local network as the client (even IP addresses just one or two digits off could be entirely separate networks).
In your case, if you're using a pool of NAT addresses your benefit of this service is severely restricted.
There are two options that I can see, though.
One is to set a custom NAT rule (assuming your firewall supports it) so that all connections to Apple's update server are NATted via the same address.
The other is to run your own Software Update Server. However, this only caches OS updates, not App Store updates, and requires configuration on each client, so you do miss some of the advantages of the Caching Service.