In this paper, we present Probabilistic ADdressing (PAD), a virtual coordinate based addressing mechanism that efficiently deals with dynamic communication links in wireless networks. PAD estimates statistical distributions of hop distances between nodes to (i) assign fuzzy routable regions to nodes instead of discrete addresses, and (ii) provide a distributed storage service to store and retrieve node addresses. We evaluate PAD both in simulations and in widely used testbeds. Our results highlight the graceful topology maintenance and recovery of PAD in challenging networking conditions due to node mobility and unstable link conditions. Precisely, we observe that, when compared with the state-of-the-art, our proposed mechanism achieves an order of magnitude fewer address changes in the network translating into less overhead traffic and high packet success.