Embodiments are directed to geo-fencing and methods for ensuring the number of elements in a given cache entry in a geo-fence server is consistent, and managing requests to retrieve cache elements from the geo-fence server for use by a mobile computer device. Having determined whether the grid tile within which a mobile computer is located is wholly within the page boundary of a page of geo-fence data, a geo-fence server provides the page to the mobile computer device if the number of geo-fences in the page does not exceed a predetermined number of geo-fences. Otherwise, the size of the grid tile is reduced by a depth index. The geo-fence server then determines if the new smaller grid tile is with the page boundary and performs repeats the process until the appropriate page having an appropriate number of geo-fence data therein can be provided to the mobile computer device.