If you have a SFF or SD chassi i think that you need to replace the CPU fan AND heatsink. There are some issues with some of them that sound like your problem. The fan in the SFF and SD chassis comes as a assembly with both heatsink and a mounted fan, really easy to replace.
If you have the SMT "tower modell" the fan has a thermal resistor in the fan housing it self that is probably the broken part. So for the SMT you probably just need a new fan. good luck.