Agent mobility presents challenges to the design of efficient message transport protocols for mobile agent communications. A practical mobile agent communication protocol should provide location transparency to the programmer and thus need to keep track of the movement of an agent. In addition, because of the asynchronous nature of message passing and agent migration, how to guarantee the delivery of messages to highly mobile agents is still an active research topic in mobile agent systems. In this paper we propose an efficient mailbox-based algorithm for inter-mobile agent communications. The algorithm decentralizes the role of the origin (home) host in locating an agent. Furthermore, by separating the mailbox from its owner agent, the algorithm can be made adaptive and is efficient in terms of location updating and message delivery. In the cases that mobile agents migrate frequently but seldom communicate, our algorithm turns out to be preferable.