Clock network delay + internal cell delay > Minimum timing requirement

The project you added didn't compile(and looked like it would take a number of changes to weed through everything.) I did notice that the databus you're concerned with is bidirectional, so there should be two Tco requirements, one through the OE register and one through the data register(I'm not positive, but am assuming). The OE path will usually be slower because it takes longer for the driver to "turn around". That being said, many interfaces don't need to turnaround in one clock cycle. So the data would need to meet the 7.5ns period, but the OE path does not. Just another possibility.

But yes, before PLLs, it was relatively common that users chose faster speed grades to achieve IO performance rather than faster internal performance. (CPLD speed grades used to be based entirely on pin-to-pin delays, i.e. the speed grades would be -30, -45, etc., meaning a 30ns Tpd or 45ns Tpd.) So you might reach a point where the faster speed grade is the only solution.