The P4 650 is a LGA775.
I know for a fact that the Stock Fan runs at 5000rpms.
The Heatsink also comes with a thermal Pad attached.
I installed one of these before and had the same temp issues. I took it all apart and behold, the fan and heatsink weren't mounted completely to the motherboard. The LGA775's have a funny mounting system. You think they are completely locked into the MOBO, you don't want to apply too much pressure so you don't snap off the stupid plastic mountpins. But, actually you need to use like 2000 pounds of pressure to get those suckers locked into the MOBO. After getting rid of the nervousness to apply too much pressure and screw it all up, I gave it everything I had and all four pins clicked right into place.
This may or may-not be your issue, but it's worth a try. Also it's also note worthly to remember that thermal compound and thermal pads need a few days to set. They heat up and dry constantly. The AS5 was a good thing though. It's much better than the thermal Pads. Thin, Thin, Thin, layers though....