This paper is concerned with the design of efficient algorithms for mobile agent communications. We first describe a novel mailbox-based scheme for flexible and adaptive message delivery in mobile agent systems and a specific adaptive protocol derived from the scheme. Then we present the design and verification of a path compression and garbage collection algorithm for improving the performance of the proposed protocol. Simulation results showed that by properly setting some parameters, the algorithm can effectively reduce both the number of location registrations and the communication overhead of 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 of mobile agents cached by hosts in the network.