We used to use those same exact heatsinks at Intel in the validation lab. At the time, they were using them on 3.6GHz Prescotts (Substantially hotter than your P4, I'm sure) and they run stable for days at a time with a fairly puny fan. I don't believe a change of heatsink should be necessary.
If it IS a heat issue, you should be able to reproduce it by loading your system for about 15 minutes until it reaches its maximum temperature. Memtest does a pretty good job of this, so if it run for hours, heat is probably not the problem.
Incidentally, about two weeks ago, I was working on a P4 3.0 GHz HP Media Center PC and it had a 'screen blanking' issue. I would boot into Windows and the screen would go blank sometimes... sometimes immediately, other times over a period of hours. I couldn't reproduce it reliably, but when this happened, it would never POST (blank screen) after a restart. I just let it have to sit for awhile and then it would start working again. Also, sometimes even when it did work fine, I would restart it and it would not POST.
What did I do to get the computer back on? Other than just letting it fix itself (had to leave it alone for several minutes to a few hours), the only solution that seemed to work 100% of the time was to unplug ATX connector from motherboard... and no, unplugging the AC cable out of the power supply didn't work either.
The problem kept coming back. I tried another power supply and the problem seemed to go away temporarily. Sure enough though, it happened again.
The CPU was running pretty hot, so I reinstalled it with some fresh thermal paste. The problem didn't come back for awhile; however, it started happening again. I put a large fan on it and run it full blast to rule out a cooling issue - again, the screen would still blank and the computer would not POST afterward until I either waited a couple of hours or pulled the ATX connector out of the board.
As it turns out, reseating the memory, reseating the heatsink, reseating the PCI cards were all things that seemed to fix it, although temporarily. Eventually, I noticed that ANY reasonable amount of pressure I put on the system board seemed to fix the issue. My guess? Something needed to be reworked on the board because some component wasn't making good contact.
The solution was to replace my client's system board. It's been about 1.5 weeks and the issue has not reoccurred since. The problem has a striking similarity to yours, so I thought you might like to hear that.