Using a powerful combination of experiments and simulations we demonstrate how the microstructure and its time evolution are linked with mechanical properties in a frustrated, out-of-equilibrium, particle gel under shear. An intermediate volume fraction colloid-polymer gel is used as a model system, allowing quantification of the interplay between interparticle attractions and shear forces. Rheometry, confocal microscopy and Brownian dynamics reveal that high shear rates, fully breaking the structure, lead after shear cessation to more homogeneous and stronger gels, whereas preshear at low rates creates largely heterogeneous weaker gels with reduced elasticity. We find that in comparison, thermal quenching cannot produce structural inhomogeneities under shear. We argue that external shear has strong implications on routes towards metastable equilibrium, and therefore gelation scenarios. Moreover, these results have strong implications for material design and industrial applications, such as mixing, processing and transport protocols coupled to the properties of the final material.