Searching for objects is a fundamental problem for popular peer-to-peer file-sharing networks that contribute to much of the traffic on today's Internet. While existing protocols can effectively locate highly popular files, studies show that they fail to locate a significant portion of existing files in the network. High recall for these "rare" objects would drastically improve the user experience, and make these networks the ideal distribution infrastructure for user-generated content such as home videos and photo albums. In this paper, we examine simple techniques that can improve search recall for rare objects while minimizing the overhead incurred by participating peers. We propose several strategies for multi-hop index replication, and demonstrate their effectiveness and efficiency through both analysis and simulation. We further evaluate our simple techniques using detailed traces from a real Gnutella network, and show that they improve the performance of these overlays by orders of magnitude in both lookup success and overhead.