1. Think positive: it may be annoying, but a computer that DOES turn off because of overheating is better than a computer with a "lemme shutdown or else I will melt and make my owner angry." system that does not work and turns your computer into a pile of garbage.
2. What you said about dust is probably true. I could clean it for you (for a couple of beers, probably) if I lived near you. It would be cheaper than buying all those things.
3. I don't know if you run Windows, Linux or Mac on your laptop, but there are programs that take cares of your fan speed, HD and processor temperatures. Try installing than and keep an eye on their values. Compare than with your laptop manufacture values (i.r: acer, sony, lenovo, apple values for "safe computing")
4. Think positive: it could not turn off and the heat would melt your computer.
5. You can check all this values at the BIOS of your laptop. I don't know how to enter into Apple's openfirwmare (their BIOS), but PC based laptops you just hit del as soon as you turn it on. There will be a field with these values (temperature and fan speeds).