The Short Messaging Service(SMS) which has become very popular in cellular networks is very highly priced. We show in this paper how self-organizing ad-hoc networks can be used to provide the short messaging service, at a much lower price. We propose a routing protocol for wireless messaging networks, which explores the characteristics of ad-hoc network routing in which mobile nodes are allowed to relay in place of static nodes. We demonstrate, using simulations, how this increases connectivity in the network and decreases the required node density for full connectivity. As our scheme relies on the delay tolerant properties of short messages, we explore the delay characteristics of our routing scheme as well.