Mobile Agent is regarded as a promising paradigm for future distributed computing. Among essential features of mobile agents, communication is a fundamental ability that enables mobile agents to cooperate with each other. But the presence of mobility raises a number of new challenges in designing message delivery protocols for effective and efficient communications between mobile agents, especially the Communication Failure and Message Chasing problem for highly mobile agents. In this paper, we firstly discuss ways to solve Communication Failure, and then describe a two-dimensional solution space for designing inter-agent communication protocols. We also propose a reliable and efficient mechanism for mobile agent communication named MEFS, which is implemented flexibly and adaptively. The MEFS provides a location-transparent tracking mechanism and, in particular, guarantees message delivery under any condition in a fault-free network. The experiments demonstrate the performance of MEFS too.