We introduce multiple validations (MV), a statistical paradigm that can be applied to a variety of large-scale optimization problems in sensor networks (SNs). MV works by resampling the underlying space of the optimization inputs, multiple optimization runs, and clustering the output solutions. We discuss the degree of freedom in resampling the inputs, so as not to change the combinatorial aspects of the optimization problem. As a driver example, we show how MV can be effectively applied to location discovery in SNs, where it is used for not only finding the nodes' locations, but also for outlier rejection, finding the confidence interval of the locations and finding the nodes' trust indices. We show how the approach is robust, while amenable to optimizations in distributed settings. Experimental evaluations on location and distance measurements from a variety of SN testbeds show the effectiveness of the approach. For example, MV-based localization almost completely removes outliers for more than 50runs of the algorithm in presence of 20% noise.