Instant messaging (IM) services enable real-time text and multimedia exchange and online presence awareness. Users typically log onto instant messaging services persistently to discover available friends and also to be discovered. However, our analysis shows that the frequency exchange of presence information incurs massive power consumption to mobile devices over cellular or wireless local area networks. Such power consumption penalty can render persistent-instant messaging infeasible for battery-powered mobile devices. In this paper, we propose several solutions to mitigate the power consumption problem. By reducing the network access and keeping mobile devices in the sleep mode as much as possible, these solutions achieve significant power saving. The power consumption of the proposed solutions is derived analytically in this paper and the proposed solutions are implemented using a Jabber-based architecture. Actual power measurement results show that the power consumption of the proposed solutions agrees well with our analysis, and significant power saving can be achieved on mobile handsets with our low power consumption solutions implemented.