Services for locating mobile objects are often organized as a distributed search tree. The advantage of this approach is that the service can scale as a system grows in size and number of objects. However, a potential problem is that high-level nodes may become a bottleneck affecting the scalability of the service. A traditional solution is to also distribute the location information managed by a single node across multiple machines. We introduce a method that radically applies distribution of location information such that the load is evenly balanced across all machines that form part of the implementation of the service, while at the same time exploiting locality.