CdTe(111)-GaAs(001) and CdTe(001)-GaAs(001) heterostructures were synthesized through molecular-beam epitaxy. In situ monochromatic x-ray photoemission spectroscopy and reflection high-energy electron diffraction, together with ex situ cross-sectional transmission electron microscopy, were exploited to probe the relation between overlayer orientation, residual strain, and the band discontinuities. CdTe(001)-GaAs(001) heterostructures appear fully relaxed even at the lowest overlayer thicknesses explored through the formation of a misfit dislocation network. Correspondingly, the valence-band maximum in the CdTe(001) overlayer is found 0.07--0.09 eV below that of GaAs(001). In CdTe(111)-GaAs(001) heterostructures, we find that residual strains are gradually accommodated within a 200-\AA{}-thick CdTe layer near the interface. The average position of the valence-band maximum in CdTe(111) is 0.09--0.11 eV above that of GaAs(001) at the interface. The difference in valence-band discontinuity for the two interfaces is qualitatively consistent with that expected from the effect of the residual strain on the valence-band maximum of CdTe(111).