I agree it does seem strange, it took me quite a bit of reading before I understood why this was the case. Not many authors or manufacturers talk about this.
With a smaller sensor, the lens has to focus all that detail onto a much smaller space. That means that the lens has to be all that much sharper to take advantage of all those megapixels. I don't believe I've ever seen a lens that was so sharp that it would provide you with full sensor resolution on an APS-C sensor.
Take for example the new king of sharpness, the Sigma 85mm F1.4 DG HSM A. On a Nikon D750, it provides the full 24Mpix of resolution (36Mpix on a D810), while on a D7100, only 20Mpix, and on a D500, only 19Mpix. That's really impressive performance on APS-C for any lens, but you can see by that example, that it's not up to providing a full 24Mpix on an APS-C sensor.
In general, the larger the sensor, the more forgiving it is, because there's a larger surface area to focus on.
The interesting corollary to this is that often, full frame lenses are built to lesser tolerances (or were, before full frame sensors started reaching resolutions that provide the same level of challenge as an APS-C sensor does) than APS-C lenses. For example, my Nikon 28-300mm f/3.5-5.6 ED VR lens gave very poor performance on my Nikon D7000, but it's quite a bit improved (though still not super sharp) on my D750.
Hope that helped!