IIRC Celeron cache being on die was actually faster as it was on die, this was mitigated on the Pentiums by there being more of it. It seemed like in games the faster cache performed better.

Another thing that helped the Celeron overclocking craze is Intel seemed to damage the brand badly out of the gate. The original Celerons had no cache at all, performed terribly and took a beating in PC reviews. So even though the A variants were much better this still had a stink on them.

The thing that probably helped the Celeron the most with overclocking though was they gimped them by only giving them a 66mhz front side bus speed. Since you had to increase this number to push the locked multiplier CPU speed up this was an advantage if you were going to overclock as you could buy a capable motherboard and run it at stable 100mhz. Whereas you'd have a lot more system wide problems trying to push a Pentium's 100mhz bus higher.