I have suffered random shutdown on and off on my Toshiba P20 for about 2 years now. I took it back to Toshiba in the first year, under manufactures warranty. They cleaned the heat sinks. After a few months the same problem reoccurred. I decided to clean heat sinks myself with compressed air, this helped a bit but still got recurrent shut downs, sometimes repetitively within minutes. I thought the shutdowns were more frequent since the Toshiba service. I finally decided to open the cooling/CPU system and thoroughly clean heat sink and replace the thermal grease.
In the removal process I found a lot of grease between the CPU and heat sink I thought it was an excessive amount. I have since smeared a minimal layer of grease covering the entire contact surface on the CPU. Since reassembly and testing under load (video rendering CPU at 75% sustained) I have not experience a single random shut down. I believe that the excess grease was the culprit, forming an insulating barrier rather than assisting heat transfer.
I do blow the heats sinks with compressed air regularly, to maintain air flow. I live in Australia with temps often in the high 20's, I do not use a cooling pad
I would like to get a hold of that laptop that shuts down within minutes for a song, as I think it is just clogged fins and excess grease