Static logic should also not depend on the rate of change either, so beware: even apparently static designs may have dynamic elements in them. Point being, I believe I have read a few datasheets which state that the clock frequency shouldn't be removed or changed suddenly, but gradual over some rate.
Chips with PLLs (e.g., PICs with superlative core clock) are one example. I want to say I've come across such a warning in an ATmega datasheet as well.
FWIW, I've played with a Z80-CPU before; this is 1980s vintage NMOS (all built from N channel FETs and pullup resistors only -- the sucker takes 200mA at 5V regardless of clock rate or bus activity!), which contains dynamic logic and, I believe, pooped out much below 2MHz or above 6MHz (rated for 4MHz nominal). Crappy clock signals cause the core to simply freeze. The earliest problem I had with it was power-up: a crystal oscillator requires miliseconds to stabilize, in which time the CPU has already forgotten what it was doing. A power-on delayed reset circuit is mandatory for this type of circuit -- and recommended for pretty much everything else, too (apparently, ATmegas have problems with very slowly rising power supplies -- better safe than sorry, use a reset circuit).
Tim