We study the resilience of structured peer-to-peer (P2P) networks in the presence of churn. Using the lifetime-based failure assumptions, we first show that a realistic churn model has an equivalent uniform failure model in the steady state. We then determine via percolation analysis and simu- lation the gap between the size of the connected component and the reachable component of a randomly picked node for Symphony and Chord. This gap represents the price of structured routing: the size of the set of nodes that are reachable by any unstructured routing method (e.g. broad- cast on the unstructured overlay) from a randomly picked surviving node, but are not reachable using structured rout- ing on the structured overlay. As an illustration, for 24- minute average node lifetime with 1-minute average node- search delay, the gap is around 12 thousand nodes or 1.2% in a Chord network of around 1 million nodes. We finish by discussing potential techniques to mitigate the price of structured routing.