As Grids try to achieve optimal and balanced utilization of unused resources in a distributed system, fast and efficient discovery of resource states is a key requirement. For small to medium scale Grids, solutions such as the approach in Globus work fine. However, for large, up to global-scale Grids, this approach is not efficient and does not scale. Additionally, even for smaller Grids, a centralized solution will always be a performance bottleneck and a single point of failure. In this paper we investigate the applicability of a structured peer-to-peer system (overlay network) for the discovery of Grid resources. Each node in the Grid becomes a peer in the overlay network, which provides a distributed directory service that allows the participants to discover resources and maintain resource states. Overlay networks implicitly balance load, scale well to very large numbers in terms of nodes and data, and meet the partial failure property of distributed systems, i.e., the system remains operational despite partial failures. We will outline a proof-of-concept implementation based on our P-Grid overlay network, present experimental results from a large-scale deployment on PlanetLab and discuss the pros and cons of overlay networks in the context of Grids.