The mobile IP (MIP) protocol for IP version 4 provides continuous Internet connectivity to mobile hosts. However, currently it has some drawbacks in the areas of survivability, performance, interoperability with protocols for providing QoS. We have proposed an alternative protocol, mobile IP with location registers (MIP-LR), which overcomes some of these drawbacks and is closer to the "service node" database approach used in the public switched telephone network (PSTN): before launching a packet to the mobile host, the sender first queries a database, called the home location register (HLR), to obtain the recipient's current location. MIP-LR is designed for operation in enterprise environments or within logical administrative domains. We focus on showing how MIP-LR enhances the survivability of MIP by eliminating some of the functions which MIP introduces for mobility support, allowing the HLR to be placed outside the mobile's home network in case the latter is particularly vulnerable, and replicating and distributing HLRs. We present two schemes for managing the multiple HLRs and enabling mobile and correspondent hosts to dynamically discover the addresses of the HLRs serving a given mobile host. The first scheme introduces a set of translation server (TS) databases while the second uses a form of quorum consensus based on the triangle lattice (TL); for the latter we present an enhanced protocol called the optimistic TL(OTL). For both schemes we present algorithms for mobile host registration and packet delivery, protocols for recovery from HLR failures, and complexity analysis of the overhead involved.