I'd go with the cleaning idea. I had a Compaq laptop that started acting up, so I eventually bought a new one. A few months later I had some free time and thought I might be able to fix it up a little and give it to my dad. I took it completely apart and cleaned everything, but the primary issue is with the fins on the heat sinks. It seems most of these laptops suck air in from all around, but it all goes out through the metal fins. Once they get clogged you effectively have no air flow. I had to replace the hard drive in that one. I think the heat killed it. The thing is, laptop processors can adjust speeds and I think they just run at lower speeds when they get too hot. My bet is that the bootable linux distro you use might not be as good at managing the processor speeds to accomodate the heat. Mine never shut down (until the last couple weeks I used it), but the touchpad would get almost hot enough to burn my finger, and I almost always ran Linux! It was an AMD Sempron I think. When I finished the "rebuild" that laptop worked better than I could ever remember.
The vents get clogged easily. You can tell if they are clogged when the fan is running loud--if you can't feel a good breeze near the fan then I'm sure it's clogged. You can fix it some by just blowing compressed air into the fins on the heat sink and you don't even have to open it. I think that blows the crud back up into the laptop, so I would not expect miracles, but if it helps then you know you're on the right track. You may also want to try installing Linux.