The privacy of users of mobile devices has been at stake, with emerging systems based on the mobile ad hoc networking technology raising additional concerns. The establishment of a connection between two nodes could readily reveal information to an eavesdropper. One approach to prevent this is to provide receiver anonymity, i.e., conceal the identity of the receiver, during the establishment of a communication path. In this paper, we introduce such a scheme that improves the efficiency of anonymous discovery, balances its cost among network nodes, and can be adaptive, trading off the degree of anonymity for the receiver.