Due to the limited number of available IP addresses most computers on the Internet use dynamic IP addresses which causes problems for applications that have to maintain rout-ing tables, for example, peer-to-peer systems. To overcome this we propose unique peer identifiers in the routing tables and apply the peer-to-peer system itself to maintain consis-tent id-to-IP mappings to be used in the routing process. While this may sound like a recursive hen-egg problem we show that it is in fact possible to devise such a mapping service for realistic scenarios. Our approach is completely decentralized, self-maintaining, and light-weight. It takes into account security to provide sufficient security guaran-tees for the mappings. We also assume that the service op-erates in an environment with low online probability of the peers constituting the service