I'm going to take WR2's response a little further... Have you disassembled and cleaned it?
Depending on your laptop model, it may be very easy to access the HSF (about 18 screws removed from the bottom) - dust gets into the heatsink and becomes impossible to remove by compressed air alone which just blows the dust bunnies back to the fan, which then blows it back into the HS. By taking it apart you'll be able to find the dustbunnies and either directly blow them out or physically remove them.
There a a number of youtube videos that address disassembly of various laptops - find your model, see what is involved. If you feel comfortable attempting the cleaning yourself (some are easy, some very complicated), I would suggest that.