i prefer without paste, better contact and better heat transfer
even if you use toothpaste, it's still better than without paste...:D
there are many people using oil as their "thermalpaste"..:D
back to the topic...well, i replace my thermalpaste for every six month..
why..? because of dust cleaning schedule..:D