Java and middleware are becoming popular on PDAs and small devices with the advent of small-footprint virtual machines. In this paper, we examine agent messaging on small devices based on our experiences with Micro- FIPA-OS, which is an agent toolkit for small devices. Since agents communicate by sending and receiving messages, it is reasonable to expect that the system should minimize communication latency both within a platform and between agent platforms. We present and discuss different deployment options for connecting terminal agents with the fixed network agent community. The performance measurement focuses on messaging both within the PDA device and between the device and another external agent platform.