By taking careful account of slab thickness and adsorbate orientation effects we present, for the first time, periodic density functional calculations predicting the preference of water to adsorb in a molecular state on the ideal rutile TiO2(110) surface at all coverages less than or equal to1 monolayer (ML). Moreover, while this has been predicted previously for 1/4 ML coverage [R. Schaub et al., Phys. Rev. Lett. 87, 266104 (2001)], we show that the assertion made in that work, that dissociation is energetically unfeasible on the ideal surface, is incorrect. Our results thus resolve a long-standing discrepancy between theory and experiment and significantly improve the understanding of water chemistry on TiO2 surfaces.