Hearing the fan run doesnt mean there is actually air moving. Most of the times a overheating laptop is caused by the airway being blocked(usually by a mesh of hairs and dust).
You should try to blow into the air vent at the side of your laptop. If you blow with your mouth it is safe to blow as hard as you can, just make sure to close your eyes, or you'll have them full if dust
.
You can also try to put a vaccuum cleaner to the airvent at the bottom of the laptop on a lower setting.
If this all doesn't help you're going to have to open up your laptop(but that isn't needed in 90% or the times).
Good luck!
I agree! If you can (and don't feel bad doing this, don't do it if your worried about braking stuff,) get yourself a tube of arctic silver 5, open the laptop and unbolt the cooler from your CPU (and GPU if it's a shared heat sink, like my Dell Studio 1735, grrrr,) and clean out your heatsink and fan and clean off all of the old (and most likely hardened,) thermal compound and use some new stuff.
My warning is make sure you don't tighten the bolts that hold the cooler to the board too much or you will actually break the bolt (I made this mistake with my laptop, I haven't stopped kicking myself, because now my cpu cooler is held on with 2 of 3 bolt, yes, dell uses 3 mounting bolts which is so stupid imho,) and regardless that the mount is partially broken, I saw my temps drop by 15*C under load.
Fortunately since, my job provided a 13" MBP and I have a SB-E for games, so I actually almost never use my studio anymore (my wife uses it for browsing the internet,) but it sounds like an airflow/heat conduction issue.
My only question would be: "Does the bottom of your laptop get extremely hot under load? Almost scalding to the touch and if you have a plastic chassis, can you smell plastic when it gets loaded?"