Answer: less than 500ps Tpd, sometimes. I built a gated ring oscillator with some single-gate 74AUC packages just to see how fast it would run. The 74AUC family seems to offer the fastest CMOS gates you can buy at at moment, guaranteeing a 1.6 ns max propagation delay at 2.5V. It looks like they can be significantly faster in practice, especially if you crank up the voltage a little :-)
The circuit is very straightforward. A 74AUC14 Schmitt-trigger inverter buffers the incoming gate signal. The output of this buffer gates the oscillator through a 74AUC00 NAND date and also drives a 74AUC04 for an output driver. The ring oscillator itself consists of two additional 74AUC04 inverters plus the NAND gate. Finally, one more 74AUC04 inverter is used as a driver to buffer the output. 453-ohm resistors are used at the outputs to create 10x dividers when combined with 50-ohm terminated oscilloscope inputs. The 74AUC gates are plenty fast, but don't source/sink enough current to drive 50-ohm cables directly, necessitating the use of these 10x "probes."
I'm running them at 3.3V, which is within their absolute max voltage of 3.6V, although the datasheet says they're recommended for up to 2.7V, and optimized for 1.65-1.95V supplies.
So, how fast are they? The oscillations start 410ps after the gate signal edge and run at 360 MHz. This frequency implies a mean propagation delay for the inverters and the NAND gate of 463 ps. That's very fast for gates you can essentially treat like your normal CMOS friends (except, of course for the fast edge rates, discussed below).
While the oscillator startup time of 410 ps is impressive, this circuit generates runt pulses at the end of the gate interval, unless the gate time happens to be an even number of cycles of 360 MHz. You can see a runt pulse generated at the rising edge here:
If this oscillator were driving a counter, that last pulse might or might not be counted. And, of course, the actual oscillation frequency will vary with voltage, temperature, and individual parts. Actually using this thing would be a non-trivial exercise in calibration.
I'm impressed with the 74AUC gates. When I built a similar circuit with 74AC gates, which I used to consider "fast," I measured a startup delay of 2.5 ns and frequency of 76 MHz. This circuit starts up 6 times faster and oscillates almost five times as fast. I think the only way to go faster is to switch to ECL parts, which I might as well try since I've gone this far.
While I had the circuit on the scope, I took a look at the edge rates from the 74AUC04's. The rise time was 560 ps and fall time 528 ps. This is not much faster than the 74AC gates which I measured at 700 ps and 650 ps, respectively. This may be part of the reason the 74AC series had such a reputation for bad behavior - the sharp edges manifest transmission-line effects on relatively short traces, even though the clock rates may not be that high. The 74AUC gates, on the other hand, actually seem to show propagation delays shorter than their edge rates, which is impressive - but I'm not convinced this is the case yet. I'm waiting on a few adapters so I can connect these outputs directly to the scope without using cables. At these speeds, dispersion in the cables might be affecting the edge rate measurements.
@Yann Guidon / YGDES asked about frequency vs supply voltage. Here it is:
The datasheet says 0.8-2.7V, but it worked down to 0.6 and a little below in my tests. You could probably make a half-decent PLL with this thing, especially below 200 MHz.