I have a 20" that has been running for some time without re-applicaton of paste.
I'd changed the HD and after thorough cleaning of both location faces, found myself with a dried-up tube of thermal paste. Perhaps foolhardy, but I decided to refit the base regardless. That same iMac has been running faultlessly even with extensive use of music videos, so I assume that it has a fairly high tolerance for high temperatures. Having said that, as this serves as a valid reminder of an additional task to be performed, it will be completed this weekend.
For info, the early G4 iMacs have the one location for application of thermal paste. Later ones (believe it's the USB 2 models) have two separate locations that require thermal paste application. I'll post photos when I get a moment.