Due to the limited number of available IP addresses most computers on the Internet use dynamic IP addresses which cause problems for applications that have to maintain routing 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 consistent 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 guarantees for the mappings. We also assume that the service operates in an environment with low online probability of the peers constituting the service.