Microcontrollers (well, some anyway) CAN be overclocked to very high levels and still work reliably.
This is due to:
-small die size and high %% od speed reserve.
This is not an Athlon, which heats as a small powerplant. PIC12C5xx, 16Fxx and similar are small beasts, which do not run into serous thermal problem when overclocked.
-Microcontrollers are made to work in quite wide voltage conditions. So, if it has to run at 2.7-5.5V at specified clock freq. it will have speed problem at 2.7V-if anywhere.
If you can guarantee narrower voltage supply region at the upper region (like 5-5.5V), you might be able to make it run at significantly higher freq.
-Many models have internal oscillator for external quartz, which might fail to run reliably with much faster quartz.
Usually one can tweak external components or just plug in external clock signal.
After this also the declared temperature range might be a problem, so don't rely for it to work at full industrial temperature range, but near room temperatures should be O.K.
All said goes for homebrewing, not proffesional use.
I have toyed with 12C509 and had it run at 16 MHz, and also had decent results with a few PIC16F84 and all Atmel's AVR's I could find.
Other part of the story is that it is almost never needed, well I didn't need it.
Usually one needs special clock rate to match some baud rate etc.- not very high clock rate.
Almost always I found that rethinking code can be greater satisfaction and bring you greater speed improvement than simple throthling RPMs...