Pentium 3.
Pentium Pro only went up to 200MHz, Pentium 2 up to 450MHz. Pentium 3 came out in 1999, at 450/500MHz.
At the other end of the scale, my P3/800 used PC-133, and there were P3s up to 1100MHz with a 100MHz FSB and 1400MHz with a 133MHz FSB. That's the kind of system where 300 clocks is feasible for a code cache miss.
After that, DDR appeared, and memory finally started to catch up with the CPU. But prior to that, you had
Possible in any cache scheme. If instruction x+1 is a branch target, it can be both more recently used and more used recently than instruction x.
That depends upon the type of code you're writing. Obviously, branches which are "exactly" back-to-back are rare, but test,branch,test,branch isn't that uncommon; an extreme case is code which embodies a domain of knowledge, classifying its input then applying the corresponding rules (IOW, something akin to a Lisp "cond" statement, except that you would normally try to use a hierarchical decision tree rather than performing the tests sequentially).
That's fine if you have a handful of common primitives and the rest are rare, but glancing over Python's primitives, I'd say that fully half of them are common. The kind of code which would only use a handful of primitives is the kind of code which you would write in C.