My p4 idles at 81F and peaks under HEAVY load at 104F. That's 27C and 40C for fans of the metric system. And Giancarlos that is with a stock heatsink and fan.
A lot of over heating problems come from not keeping the cpu heatsink fins cleaned out. You would be surprised at how much of a difference it makes just blowing out the dust bunnies. The fan arrangement in the case is another. If the exhaust fan(s) are close to the cpu fan then running at full speed tends to starve the cpu fan making the chip run a little warmer than desired. Reducing the exhaust fan rpms helps to reduce the starvation of the cpu fan. My Cooler Master Aerogate II was money well spent. With it I can balance the fans in the case making a more efficent air flow through the case. And as a added bonus it reduces the noise. I have low noise fans to start with but this controller helps even more.
Now software wise if a lot of things are running in the background it makes the cpu work constantly. When the cpu is doing something it gets warm. Streamlining the unneeded services is one way to reduce the workload. Another is to do away with wallpaper and any programs that monitor the system. Leaving something like MSI's corecell program running will make the cpu work constantly and that makes it run warmer than it really needs to.
It really doesn't matter if you have Intel or AMD, a lot of the heating problems are easy to fix. You just have to use a good logic train to sort them out.