We have completed an experiment to obtain diffuse scattering data for use in a comprehensive study of the local-structure changes as a function of molybdenum composition and have made large strides in interpreting some of the major changes found in this study. For these experiments, single crystals of molybdenum substituted VO2 with the formula V1-xMoxO2 were synthesized, with molybdenum compositions up to x = 0.60, using a novel, two-step chemical vapor transport synthesis. Using these large single crystals for total scattering experiments, we report the discovery of the sudden collapse of three-dimensional order in the low-temperature phase of V1-xMoxO2 at x = 0.17 and the emergence of a novel frustrated two-dimensional order at x = 0.19, with only a slight change in electronic properties. Single crystal diffuse x-ray scattering reveals that this transition from the 3D M1 phase to a 2D variant of the M2 phase results in long-range structural correlations along symmetry-equivalent (11L) planes of the tetragonal rutile structure, yet extremely short-range correlations transverse to these planes. Additionally, we report a combined study using single crystal X-ray diffraction, powder X-ray diffraction, and representational analysis to examine both the local and crystallographically averaged atomic structures simultaneously near x = 0.50. Between about x = 0.50 and 0.60, the average structure of V1-xMoxO2 is the parent rutile phase, but the local symmetry is broken by atomic displacements that are best described by an orthorhombic cell in the spacegroup Fmmm. This model is locally identical to the two-dimensionally ordered 2D-M2 phase except the correlation length is much shorter in the 2D plane, and longer in the frustrated one, making it more isotropic.