1 Service discovery in mobile ad hoc networks (MANETs) is a challenging issue. The nodes in a MANETs offer spontaneous and variable connectivity. Also the proximity of a given service as well as the kind and the number of services vary unpredictably with time. Traditional directory based architectural solutions can hardly cope with such a dynamic environment while a directory-less approach has to resort to network-wide searches. Some solutions integrate a Service Discovery Protocol (SDP) with the routing protocol. These can improve performance but still there is need for network wide searches which is a source of inefficiency. There has been lot of work on the problem of service discovery by leveraging on the random walk based search in wired peer-to-peer networks. These works present interesting results that can be useful for MANETs and can be good candidates for SDP, as these methods require fewer resources as compared to SDPs using some sort of flooding. In this paper we have tried to identify some of the open problems in service discovery in MANETs that use random walk.