Highly dynamic overlay networks have a native ability to adapt their topology through rewiring to resource location and migration. However, this characteristic is not fully exploited in distributed resource discovery algorithms of nomadic resources. Recent and emergent computing paradigms (e.g. agile, nomadic, cloud, peer-to-peer computing) increasingly assume highly intermittent and nomadic resources shared over large-scale overlays. This work presents a discovery mechanism, Stalkers (and its three versions—Floodstalkers, Firestalkers, k-Stalkers), able to cooperatively extract implicit knowledge embedded within the network topology and quickly adapt to any changes of resource locations. Stalkers aim at tracing resource migrations by only following links created by recent requestors. This characteristic allows search paths to bypass highly congested nodes, use collective knowledge to locate resources and quickly respond to dynamic environments. Numerous experiments have shown higher success rate and stable performance compared to other related blind search mechanisms. More specifically, in fast changing topologies, Firestalkers version exhibits good success rate, low latency and cost in messages compared to other mechanisms.