Yes you should unless the heatsink/fan combo comes with its own and advises against it. Even if they supply their own thermal tape (usually taped to the bottom of the heatsink), I always clean this off using rubbing alcohol or peroxide (yes, use sparingly as using this is not orthodox at all but in the absence of alcohol is fine by my book...). The reason for this is that Artic Silver and other commercial thermal paste is almost always superior than the one included with even the best heatsinks.
Link Removed due to 404 Error
I recommend Artic Silver. But anyway, Pentium's have been running hot since their hay-day and the Pentium-D is no different. You should notice a significant difference in temperature by using a retail heatsink/fan. But the reality is your computers, if they are being used for basic office apps only, will never approach full load. Your CPU will probably never hit the TJMAX (the point at which the CPU burns up or throttles down). Remember, newer Intel CPU's will throttle down the stepping on the processor to keep the processor working at temperatures below critical levels. It does not sound like your computers are in imminent danger of overheating.