Mobile IP is one of the dominating protocols that provide mobility support in the Internet. However, even with some proposed optimization techniques, there is still space for improving the performance. In this paper, we present a mailbox-based scheme to further improve the performance. In this scheme, each mobile node migrating to a foreign network is associated with a mailbox. A sender sends packets to the receiver’s mailbox, which will in turn forward them to the receiver. During each handoff, a mobile node can decide whether to move its mailbox and report the handoff to the home agent, or simply to report the handoff to the mailbox. In this way, both the workload on the home agent and the registration delay can be reduced. Also, the scheme is adaptive. By applying the dynamic programming to compute the optimal mailbox’s migration policy, the scheme can make the total cost minimized.