Ok....to clear some things up for you man..
Stock heatsinks come with whats called a thermal pad. If you would have looked under your heatsink you would have noticed a almost rubbery textured little (generally blue) square.
Most processors don't need to have any paste on them for them to work at safe temperatures.
That for the most part is incorrect, especially when dealing with the AMD64's....go to a site where they say it's not needed...which I believe you'd have a hard time finding.
Like I said, stock heatsinks come with a thermal pad on it. You DO need to have thermal paste on a heatsink, but not a retail one.
You DO NOT put thermal paste on a stock heatsink that already has a thermal pad. However, if you get an aftermarket heatsink you do infact need to put thermal paste on it.
70 degrees C is the optimal operating temperature for Athlon 64's.
Wrong
You said your processor was running 41 degrees C. This is nowhere too hot. 70 degrees under a heavy load is fine. Some run at over 100 C when they overclock.
Even more incorrect
The only part of that sentence that is correct is the 'This is nowhere too hot'
41C is a fine temperature, infact it's really pretty dern good for the AMD64, but it of course also depends on your temp in the house.
a CPU at 100C = a dead CPU, there are no CPU's at 100C when overclocked, so wherever you got that idea Reverse, you need to forget it as you'll lead people like him who don't know, to trouble.
Overclockers especially keep their CPU's cooler than everybody, no one in their right mind would let a stock CPU get up to 100C, infact it's impossible. The AMD64's have a thermal shut off temp of 70C which is infact too hot.
I would say the maximum you want that 64 to hit is 60C and even then I'd suggest you look into better cooling to sustain the life of the CPU.
To recap: Retail heatsinks come with a thermal pad. You do not put thermal paste on a stock heatsink that already has a thermal pad.
You do put thermal paste on an after market heatsink, and failure to do so will get you much higher temps so I would suggest never installing a heatsink without paste.
60C is a decently safe temperature, but like I said even then if it's 60C at full load I'd still suggest looking into getting your system a bit cooler although yes I will say that the CPU should have no problem surviving those temps.
70C is way too hot though, which is why they have the shutoff feature at that temp.
Hope that helps