How I do underclocking - drop the CPU voltage to as low as the motherboard supports. Then lower the CPU's clock speed accordingly. Example - Tbred 1700. Dropped it down from default of like....uh, 1.65V? to, I believe it was 1.3V. Then I dropped the multiplier to 5.0, but kept the FSB at 200MHz. Result - 1GHz CPU, with low heat and power usage.
Even so, just make sure there's still adequate airflow over the heatsink. Modern CPUs do still generate a lot of heat, even when fed less power.
I would also recommend you find a really quiet fan. There are 80mm fans out there that are nearly silent. Maybe snoop around
Silent PC Review for a little while. There is
a section there, toward the bottom, about quieting your fans down. That's probably most advisable. Passive cooling is best left to things like the chipset, and maybe even the videocard, with one of those big wrap-around heatsinks - or just a really old videocard, like some 8MB ATi Rage thing - that doesn't need active cooling.
Ooh, just saw that you said they smoke. That stuff will coat heatsinks in a slightly sticky layer, to which dust will adhere well, effectively insulating them.
Hm....well, the PC will need airflow. If it put out the heat of a 386, maybe then you could seal it up and rely on the case to radiate the heat away.
Maybe give it a powerful, yet well-filtered intake fan? And impress upon them that it must be cleaned regularly. At least the filter might catch some of the tar in the air, and at the very least, the dust.