Apple didn't used to use thermal paste as late as the B&W G3s. I doubt the early Yikes! based G4s used it either.... probably not even the Sawtooths..
I thought thermal paste didn't make nearly that much difference. That's... just odd.
Maybe it's because when I was reading about it CPUs usually hovered around 100-120F instead of the much higher temps they seem to be "enjoying" today.
perhaps it's different for laptops, but as a former pc tech i saw many a cpu burnt up from not having thermal paste or a thermal pad between the heat sink and the cpu. basically what it does is allow the imperfections in the heatsink and the cpu surface to mate together, allowing better heat transfer between the two. it also fills any gaps between the two to once again keep the heat moving, as air sucks at conducting heat! it's interesting that they didn't use cpu paste in the past, but it's possible their clamp system kept the two solid against each other, or perhaps the chips just didn't generate enough heat? i don't know enough about those machines to say one way or the other.
one of the problems with heat sink paste is that too much can function as an insulator, rather than a conductor. that's what people seem to be seeing here, but honestly, if it's properly clamped down it should be squeezing most of that muck out anyway, which is why it looks so messy in the pics. if you look closely, for the most part the layer between the chip and the heatsink is pretty thin (of course my eyes aren't what they used to be), but there's gobs of the stuff around the chips from getting squeezed out. i think this is why you see varying results from replacing the thermal paste.