In this study, we addressed four related issues concerning the estimation of traveled distances in a distance-matching visual task, using a virtual reality (VR) setup. Firstly, we found that when explicit counting strategies were blocked by an interfering dual task, the performance of 35% of subjects was strongly impaired. Secondly, we found that, when encoding and test phases took place in similar perceptual contexts, subjects' performance could be extremely accurate, which suggests that the inaccuracy and variability reported in previous studies could stem from the use of inefficient mechanisms to building context-independent representations. Thirdly, by systematically manipulating the visual cues available, we ascertained that depth cues and texture regularity were not necessary to estimate traveled distances accurately. Fourthly, we evidenced two distinct groups of subjects according to their dependence on the invariance of speed. While performance remained accurate in some subjects when we manipulated the speed of the test phase it was severely impaired in other subjects, whose strategy seemed to rely on an implicit, time-based estimation. We suggest that the existence of these different groups could account for the inaccuracy and variability observed in previous studies.