Sorry for picking out a single point from your lengthy and helpful post, but increasing the voltage isn't always necessary. Indeed, some ATers have overclocked CPUs running with reduced voltage (undervolting).
That's because "we need to increase the voltage to up the frequency" is a simplification.
A little bit more exactly (although still vastly simplified):
The whole problem is that we're working at the analogue level and our transistors aren't optimal. So when we "switch" the input from 1 to 0 (or vice versa) neither the output nor the input change immediatly.
I think a little picture should make that a little bit clearer:
http://img23.imageshack.us/img23/2752/cmos.png
Well if the frequency is too high we can't distinguish zeros from one any longer and we have a problem.
@power consumption: I think we should just differentiate between static and dynamic power consumption and everything is fine

static power consumption: transistors are not ideal and do not switch off completly, resulting in a small leakage current that flows even in the off state
dynamic power consumption: gates and wires have capacities that must be charged or discharged during the switching process
Traditionally dynamic power dominated static power, but in the last years they contribute almost equal parts though static power c. is growing faster. So
The formulas for the interested:
f.. frequency
C.. wire capacity
Pdyn: 1/2 * C Vdd^2 * f
Psta: Idd * Vdd
PS: Please correct me if I'm wrong, most of that stuff is hidden in the darkest corners of my brain.. brrr I don't think anyone likes that analogue stuff
