The propagation delay is heavily dependent on the supply voltage. I've
made once a ring oscillator, for the fun of it, with 74HC00. It was able to do 100 000:1 frequency sweep by simply sweeping the Vdd.

Check you have good decoupling against any power noises, with no voltage spikes or surges measured near the chip pins, and that the voltage regulator doesn't transiently go into current limiting or self oscillating (for small amounts of time, small enough to not be visible on a casual look on a slow oscilloscope).
Another thing is the slew rate, try using a trigger Schmitt input and see if it makes any difference. Maybe only some edges are too slow, not all of them, and that is why on the oscilloscope the raise/fall time appears to be OK, when in fact for some rare edges it might not be OK.
Beware that sometimes the IC fabrication process changes (upgrades), and the newer chips are much faster. This can be very bad, because the fastest a gate is, the more sensitive it will be to reflections in the PCB traces, noises and glitches. So, a circuit that used to work perfectly well with the old/slower chips, might not work properly, or might not work at all with the newer/faster version of the same chip.
Also, 10us instead of 10ns propagation at a constant Vdd is not possible. If it were to be so, no digital circuit would be able to work. Something else is happening with that board. Maybe those with 10us are from the CD4000 family and not from the 74HC, so fake chips, I don't know.
