One very likely thing that hasn't been mentioned is dust and schmutz in the case.
You didn't mention what kind of machine you had. Most of the G3/G4 towers allow you to open the side of the case -- be sure the little slide safety latch at the rear is slid in, and none of the cables at the back will foul or bind as the side it let down, then pull up on the ring latch (it may stick a bit) and ease the side down. (You can do this briefly with the machine running, but don't leave the door down for very long, particularly if running programs, as the CPU cooling is dramatically lessened!) I recommend keeping the plug in (to give a good antistatic grounding path) but the computer power off.
Look carefully in the air path of the fans (there may be several) and carefully clean out the dust, hair, etc. that has gathered. Be sure to get the fins of the heatsinks on top of the processor(s). Be careful NOT to touch any of the SMDs and other components on the motherboard itself when you clean things, however, because Macs have a (fairly well-deserved imho) reputation for static sensitivity. I try to keep a vacuum running a few inches away to suction up the stuff, but you can avoid this if manipulating the vac nozzle is at all unwieldy.
I take special care to clean the blades of the fans (with a Q-tip or similar thing, on both sides) as even a small buildup on the leading edges can really spoil the characteristics of the airflow...
When everything is dust-free, listen to the fans and be sure they are running at proper speed. I've had several G4 case fans get bad bearings -- sometimes you can relubricate them carefully, otherwise replace them BEFORE they seize up and stop when you aren't watching.
Of course, what this sounds like to me is that the heat-sink compound between the PPC chip proper and the heatsink has gone bad or developed gaps. The die is overheating (and properly shutting itself down) and the heat isn't making it up to the fins to be dissipated properly in the air current -- hence the 'room temperature' air, and perhaps the several hours before things cool down enough to start reliably. I'd be tempted to rework the heat-sinking (follow any of the threads here about how to do that) if the problem persists with a clean air path and known-good fans...