We study the role of dynamical constraints in the general problem of finding the best statistical strategy for random searching when the targets can be detected only in the limited vicinity of the searcher. We find that the optimal search strategy depends strongly on the delay time tau during which a previously visited site becomes unavailable. We also find that the optimal search strategy is always described for large step lengths l by a power-law distribution P(l) approximately l(-mu), with 1<mu(tau)</=2. Our findings appear to remain valid even if arbitrary energy costs of locomotion are considered.