Not puzzling at all, when one understands the fundamental optical law that the smaller the image circle of a lens, the higher the line-count per millimeter delivered to the film/sensor. For example microfilm lenses have always been able to resolve very tiny detail on super fine grain microfilm. In theory, a lens designed for APS-C only coverage ought to be able to resolve the same number of lines-pairs-per-picture-height as the FF lens, so that pixel count alone becomes the determining factor. But in dSLRs the FF lens is a dual purpose lens and the APS-C lens is generally more of a 'less expensive lens for amateurs' so the total resolution goal of the lens is lowered in the goal of lower cost to produce and sell.
It is an unfortunate historical fact that the very different FF and APS-C formats share a lens mount, and often FF lenses are considered dual purpose.
When I started in digital more than 8 years ago, there were no high quality EF-S lenses. So we used the crappy kit EF-S lenses together with the good quality EF lenses. It was an unsatisfactory kludge because the EF lenses were expensive and heavy, and more than half the useful image was cropped away.
Since then, Canon has introduced some very fine EF-S lenses, like the 17-55, and then the 15-85, and now the STM line. This has legitimized the format and made it much more useful for pro and amateur alike.
The FF and APS-C formats should now be considered separate lines. And indeed, many keep and use both formats, because each has their strengths. It is as in the olden days when many (including me) kept both 35mm and 120 format film cameras and lenses. (And sometimes 4x5 and larger formats too.)
With the very fine lenses now made for APS-C, the appropriate performance comparison should be FF body and FF lens against APS-C body and APS-C lens. As you suggest, they would probably come out about even for resolution.
FF still has advantages because the lens line is way more extensive, and also I believe DR is better. As well, ultimate noise performance is better because to get equivalent noise on an APS-C you would need an ISO of 25 or 50 (compared to 100 for FF), and those ISOs are not available on APS-C.
Those differences IMO are significant but mostly show up when we are light-stressed or when there are special demands. Under most conditions, the differences between FF and APS-C are not noticeable.