DHT-based routing has been proposed recently in the literature and this new routing paradigm promises several advantages (e.g. decreased state requirement) over conventional routing protocols. However, the robustness of such schemes is questionable given the difficulty of maintaining even overlay DHTs on Planetlab. In this work, we seek to address this issue head-on by taking the first steps towards a theory of the consistency of DHT-based routing. We do so by proposing the first fully-decentralized maintenance algorithm for DHT-based routing and then prove that it guarantees the property of eventual consistency. We then go on to explore a generalization of DHT-based routing, called a rendezvous service, and explain how routing protocols built using a rendezvous service may offer better convergence properties as compared to DHT-based routing. Although it is presently unclear whether DHT-based routing will ever be deployed in the Internet, we address one of the main technical objections against them: their perceived lack of robustness.