This paper addresses the issue of defining a location service suitable for very dynamic and highly populated networks (millions of users), where services might experience highly correlated peaks of traffic or synchronized access to specific servers. A cooperative mobile agent solution is proposed to solve the major problems, allowing the dynamic deployment of new application servers when needed. But it requires an adequate location service to route the clients to the application servers, which scales to a large number of clients and still allows a high number of updates. This paper presents a very dynamic location service, which adapts to overload situations by modifying the routing information distribution and (possibly) its servers’ internal structure. The responsive and fast route update results in a load redistribution, which allows it to scale to a broader range compared to other alternative approaches.