I let my system run hot and quiet. I've a K7S5A with a Athlon T-bird 1333, quite a hot chip (hotter than yours at about 70W at full load compared with 62W for your Palomino 1600+; see
Anandtech's info on power dissipation). I use an Enermax Whisper PSU with adjustable fan speed, the external fan I run at about 2000rpm to keep it quiet, and an Alpha 8045 HSF carefully fitted with a very little Arctic Silver II, with the quietest Papst fan (19CFM output), all tucked away under my desk (keeps my feet toasty warm, not much air circulation though).
At stock speed, 1328MHz on this board, it's usually 33-35C system temp, and 57-59C CPU temp, full load (I run SETI@home 24/7), in an ambient temperature of >20C (all that hot air the PC makes). It's rock solid. Overclocking a little to 1427MHz (75W), it goes up to 35-37C system temp, 61-63C CPU temp. Rock solid. (By rock solid I mean, it never crashes, and as I say it runs 24/7/365.) Even when I let the system idle at stock speed, it still runs warm at 30-32C system temp, 52-54C CPU temp.
Moral of the story, such as it is, is yes, get a better HSF, and be very careful to fit it right with a suitably small amount of compound evenly spread; these chips can run scarily hot at their stock speeds or even with a slight overclock with perfect stability. The only other consideration might be the lifetime of the CPU - at these temps your CPU may have a lifetime of only 5 years' running or so; if you keep it really cool (under 40C) you can reasonably expect it to last several decades' running.