We present the results of a study that investigated the interaction of strategy and scale on search quality and efficiency for vista-scale spaces. The experiment was designed such that sighted participants were required to locate "invisible" objects whose locations were marked only with audio cues, thus enabling sight to be used for search coordination, but not for object detection. Participants were assigned to one of three conditions: a small indoor space (~20 m2), a medium-sized outdoor space (~250 m2), or a large outdoor space (~1000 m2), and the entire search for each participant was recorded either by a laser tracking system (indoor) or by GPS (outdoor). Results revealed a clear relationship between the size of space and search strategy. Individuals were likely to use ad-hoc methods in smaller spaces, but they were much more likely to search large spaces in a systematic fashion. In the smallest space, 21.5% of individuals used a systematic gridline search, but the rate increased to 56.2% for the medium-sized space, and 66.7% for the large-sized space. Similarly, individuals were much more likely to revisit previously found locations in small spaces, but avoided doing so in large spaces, instead devoting proportionally more time to search. Our results suggest that even within vista-scale spaces, perceived transport costs increase at a decreasing rate with distance, resulting in a distinct shift in exploration strategy type.