We performed very deep searches for 2 ground-state water transitions in 13 protoplanetary disks with the HIFI instrument on-board the Herschel Space Observatory, with integration times up to 12 hours per line. Two other water transitions that sample warmer gas were also searched for with shallower integrations. The detection rate is low, and the upper limits provided by the observations are generally much lower than predictions of thermo-chemical models with canonical inputs. One ground-state transition is newly detected in the stacked spectrum of AA Tau, DM Tau, LkCa 15, and MWC 480. We run a grid of models to show that the abundance of gas-phase oxygen needs to be reduced by a factor of at least ~100 to be consistent with the observational upper limits (and positive detections) if a dust-to-gas mass ratio of 0.01 were to be assumed. As a continuation of previous ideas, we propose that the underlying reason for the depletion of oxygen (hence the low detection rate) is the freeze-out of volatiles such as water and CO onto dust grains followed by grain growth and settling/migration, which permanently removes these gas-phase molecules from the emissive upper layers of the outer disk. Such depletion of volatiles is likely ubiquitous among different disks, though not necessarily to the same degree. The volatiles might be returned back to the gas phase in the inner disk (within about 15 AU), which is consistent with current constraints. Comparison with studies on disk dispersal due to photoevaporation indicates that the timescale for volatile depletion is shorter than that of photoevaporation.