Message delivery protocols are among the most important mechanisms in a mobile Agent system since cooperating mobile Agents need to communicate with each other. In this paper, a generic framework is presented for designing mobile Agent message delivery protocols. The framework uses a flexible and adaptive mailbox-based scheme, which associates each mobile Agent with a mailbox while allowing the decoupling between them, i.e., a mobile Agent can migrate to a new site without bringing its mailbox. By separating the concerns of locating the mailbox of a mobile Agent and delivering a message to the Agent, a large space of protocol design with flexibility is obtained. Using a three-dimensional model based on the scheme, the generic framework not only covers, as particular cases, several known protocols, but also allows for the design of new ones suited for various application requirements. By extensive simulation experiments, trade-offs between design parameter selection and their impact on the performance of derived protocol are analyzed. The conclusion of analysis can be used to guide applications of the framework.