I have had this problem before, and had 2 separate causes. On the first case, I had found that the fan retention bracket had an "ear" broken off. the easiest way to check is with the computer off, try to gently tug at the fan/heatsink. If it pulls away slightly, then check the 4 "ears". Also check to make sure the 2 levers are in the correct position. If the levers are right, and you do happen to have a broken retention bracket, then they are easy to find.
Here is one place to find them.
The second time I had the problem, it turned out to be that the stock P4 fan was going out and was not turning at full speed. In this case, I would find an aftermarket fan and heatsink. Zalman makes some nice quiet ones, and also Swiftech and ThermalTake make some good ones.
Hope this helps.