We propose new mobility strategies in Mobile Information Systems (MIS): (1) Leaving Trace (LT) scheme, which effectively reduces mobility management cost. The basic idea is that putting the Visitor Location Register (VLR) ID of the Registration Area (RA) where the terminal currently resides into the registration-cancellation message, the trace of terminals is left in the VLRs visited, so that a call may be connected by querying to the VLRs rather than to the HLR when the terminal-terminated-call occurs. The LT method distributes messages to VLRs. (2) Multicasting Home Location Register (MHLR) method, which makes use of the call locality in the callee. When a call is established, MHLR records the caller`s VLR ID according to the callee. Periodically, MHLR ranks the VLRs and determine which VLRs frequently make calls to the callee. During a location registration process, MHLR sends the terminal`s location information to the determined VLRs and it can eliminate HLR queries from the call tracking. To estimate overall mobility management cost, we simulated the new methods of MIS. The simulation model is based on the Jackson’s network and makes it possible to estimate mobility management cost of MIS. The proposed methods effectively reduce mobility management cost more than the IS-41 method.