Personal communication service (PCS) networks support the delivery of communication services as the mobile user moves from one region to another. When a mobile user receives a call, the network has to quickly determine its current location. The existing approach suffers from high delay in locating the mobile since the mobile's current location has to be always consulted on the location databases. Caching the location of the remote mobile is useful to reduce this delay. However, the longer the useless record caused by the movement of the mobile remains in a cache, the higher the degradation of cache memory utilization is imposed on a system. In this paper, we propose an efficient caching scheme that a cached record is not allowed to remain over the predefined time, called a time-threshold, in a cache. A long time-threshold may cause to increase the obsoleteness of the cached record. In contrast, a short time-threshold may cause to degrade memory utilization. This paper finds the optimal time-threshold to enlarge cache memory utilization. Also, we provide a unique solution for determining the optimal time-threshold, and study the effects of changing the important parameters of mobility, calling patterns, and network conditions on the optimal time-threshold. Furthermore, we compare the performance of the proposed caching call delivery scheme and the existing call delivery schemes.