I usually apply fresh paste quite often, but it really shouldn't need to be changed very often. Once a year wouldn't be a bad interval. I can't stress this next point hard enough, you only need to use a little paste. Just a Little, 90% of the people use more than they need to. If you cut a BB in half, that would be about all I use.
Exit:
My bad, your talking about the mobo heatsinks, only one or two of those sinks can use TX-2. The others need tape. What mobo are you using?