Now that I think about it, I can't recall any of my G4 Powermacs ever having thermal paste on them....
But it would always help for sure and highly recommended!
All I have encountered has a thermal pad.
Contrary to what some are saying, the claim that thermal paste is not a requirement is dependent upon the surface of the processo, the heatsink and the mounting mechanism.
In other words, if the heatsink is completely flat (doubtful) and the cpu surface is without imperfections (doubtful) and the mounting mechanism allows for proper contact then it is possible to do without thermal paste.
As I have alluded, this is rarely ever the case unless the user has intervened by "lapping" the heatsink.
Also, do not be fooled by the idea that the low speed of the processor means it does not run hot. A modern 400MHz processor may run extremely cool while a G4, given the technology at the time, probably will not run all that cool.
It also depends on the processor of course, some run hotter than others.
Cliffnotes: Use thermal paste.