ccleaner always finds "problems" half of them are not problems (If not more) they are empty MRU's left behind after opening & closing programs. If you delete, use PC, reboot and run ccleaner again you will find some are back again.
generally I would tell people to refrain from using registry programs. They can cause for more harm than good at times. (reg cleaners don't discriminate in what they see as "rubbish")
However. I use a Thinkpad T61 at work running XP with SP3 no problems.
Seeing as MS always uses overheating as an excuses when in doubt (They could have requested you to send the dump files for analyzes or advised to download the dump file reader from their side if you know how to read them) I would say the overheating is unlikely (Unless you genuinely can feel a hot part on the laptop around the fan outlets (warm is normal, hot is not) or if parts of the laptops feel hot.
As ccleaner did help a bit I would agree the problem is software.
Again run a checkdisk (Go to my computer, right click C:\ drive, properties, tools, check disk, tick both boxes, click yes when prompted that drive is in use need to reboot message, and reboot)
This will truly fix the default MS registry properly and scan for errors.
If that fails either run a repair on windows, or install from scratch. (Trust me, reinstalling the operating system saves sooo much time! Takes perhaps half a day including application reinstall & update, but would def fix any software issues haha. If you don't want to concider it unless you got a good reason for it :)
Setting preferences is waaaay less time consuming that dealing with a problem for days and days :).