PC running very slowly even after fresh install

Just wondering if anyone can help.
My PC has been running slowly on and off over the last couple of weeks. It has been ok on start up (perhaps a little slow on occasion) but generally ok. Once running however, it would slow dramatically to the point where nothing responded and I would have to force a shut down. Sometimes this would happen quickly after start up and at other times it seemed to be ok for most (and very rarely all) of the day. It would also on occasion speed up again on its own after running incredibly slow. Basically it could be very random!
I tried all of the basic things like shutting down any unnecessary programs on start-up, running a virus check, de-frag, chkdsk, disconnecting from the network and internet etc, none of which made any difference.
2 days ago it got to the point where I thought a fresh install was my only option. After backing up all my files etc to an external hard-drive, I completed a new install on the original hard drive and proceeded to reload drivers etc.
It was immediately obvious that even with the fresh install things weren't right with the install itself taking forever and then opening explorer or even downloading updates from Windows Update would slow the computer dramatically. At this point after a read through a few threads on this and other forums I though I might have a HD on the way out.
I removed the original primary HD altogether and shifted the secondary one into it's place and re-installed Windows again (all from a genuine windows CD). The HD was formatted in the process (as it was with the primary drive) and still things aren't right.
There are absolutely no programs installed (not even any antivirus) and all I've done is install drivers for the graphics card, sound, modem and network comms. Like before, the PC is slow even trying to open explorer to view folders and has been connected to Windows Update, but like the first time with the primary HD is struggling to load any updates (took 2 attempts and about 6hrs to get some of them installed)
I've also tried running memtest86 thinking the memory might be causing the problem, but this also came back clear.
With the HD swapped and the memory cleared ok and a completely fresh install with no software loaded, I'm thinking I might be in trouble!
Any suggestions for what else could be causing the slow running would be most appreciated. The system's 5 years old and I know nothing lasts forever, but it was actually a good set-up before it's problem and I'd rather not spend a large sum of money replacing the whole thing

Open a Resource Monitor and check CPU (processes and services), memory and disk tabs. Sort by the relevant columns in each and see if you can find a high usage entry. Doesn't mean that yours is the same but I may think of svchost (netsvcs) as being one. Take screenshots and post here if you can't make out anything. Make sure to do the sorting or it won't mean much.

Does the motor get very hot? Did you try removing dust from the fan?

Just because I did that lately, and it did help a bit. Was a lot of work though, it depends on your computer... If it means taking the whole thing apart I would just start by vacuum cleaning from the side, might be enough.

Find a way of checking your CPU temps, either in the BIOS, or, a program to monitor it from within Windows...

(The thermal interface/spreading of heat sink compound on the CPU's heat spreader to the heatsink will degrade/solidify/burn off over time, and, every few years, a thorough cleaning and reapplication of something like Artic Silver will sometimes solve)