This paper is concerned with the design of efficient algorithms for mobile agent communications. We first describe a novel mailbox-based framework for flexible and adaptive message delivery in mobile agent systems and a specific adaptive protocol derived from the framework. Then we present the design and verification of a path pruning and garbage collection algorithm for improving the performance of the proposed protocol. Simulation results show that by properly setting some parameters, the algorithm can effectively reduce both the number of location registrations and the communication overhead for each registration. Consequently, the total location registration overhead during the life cycle of a mobile agent is greatly reduced. The algorithm can also be used for clearing useless addresses cached by hosts in the network.