My guess is the customer is cloning the Virtual Machine, and one of the cloned instances with the TFS instance installed on it no longer has any leases, but the cloned instance that you logged into did have leases available. This is one of the many reasons we recommend disallowing activating TFS product keys on VMs.
The only alternative explanation is that the customer is caching the binary blob responses from the TFS instance. Which might be the case if the customer's network is misconfigured (or "properly" configured to cache multiple requests that "look" similar). A good way to test this theory is to temporarily disable caching on the network.