Considering how much dust can accumulate between the fan and the heatsink in a laptop...
... did you take apart the laptop to get between the fan and the heatsink, or did you just take a can of compressed air and blow it into the exhaust port to push the dust back into the fan to break it up? Running the fan long enough without free flowing air can speed up the process of wearing down the bearings in the fan (if it isn't a bearing-free fan) or burn out the lubricant in a bearing-less fan. Which means if you wait long enough, you might need to replace the fan as well as cleaning the cooling channel.
I'm not disagreeing with you about the fact that your laptop won't shed heat well... I've got a Toshiba Satellite A75 upstairs that comes with a warning sticker to not use the laptop on your lap because of how hot the P4 3.33ghz processor gets... and that's a dual fan model. The heat sink mounts to the motherboard, so there is always heat bleeding back into the system (as opposed to the newer designs where there is a cut away for the heat sink to avoid just that).
Overheating will also degrade the thermal paste/pad on the processor, so by the time the unit needs to be cleaned, it needs to be re-pasted as well. That will help shunt some of the heat off the processor faster.
Now, you can undervolt most processors without going into the BIOS with a utility called RMClock. But don't just download it from there. There is actually a nice and comprehensive guide to undervolting here at notebookreview.com that includes using two utilities to monitor what you are doing. It's worth giving it a read-thru, and following along to see if you can indeed undervolt your processor succcessfully, and drop those temperatures.
EDIT You said you finally got this working, and that it was not very effective. At this point I'd have to ask what your temperatures were before, and what they were afterwards. Because, you really only could expect 5 to 10 degrees C reduction from the procedure. At any rate, you now want information on software underclocking... which brings us back to Kyle's comment. It's worth a shot looking though, right? I'll start you off, but at this point, it boils down to basic research... and by that I mean using a search engine and looking for terms like "overclocking software". Doing something like that would bring you to a site like this, listing 15 overclocking tools.
Since you mentioned AMD Overdrive, you should actually try it. You said you had "seen" it, but that was all you mentioned about it. However, if it does not work with your system, you might not have much luck with any of the other programs you find.
I'm the kind of person who would take apart the hardware, and clean it until it was like new, and then assemble it to the point where it worked like it was new. I am still convinced that attempting to find this software solution is just a bandage fix. The fact that you won't supply any concrete information (pictures, temperatures, etc) just adds to that. But, at any rate, I wish you luck in the underclocking.
Best Answer
Yes under clocking the CPU will cause it to produce less heat. How much you need to under clock it is impossible for us to say. Keep clocking it down and testing under load until the heat sits in a range you're comfortable with.
Having said that, it's not the processor being faulty that's causing overheating, it's your cooling apparatus.
Since it's a notebook, it's probably got at least one heat-pipe, and if that heat pipe is fractured it won't work properly and heat will build up, regardless of how clean the vents and heat sinks are or how fast the fan is spinning.
Fractures in a copper heat pipe can be near impossible to see with the naked eye, and if they happen on a seam it will make it even harder to spot.
Replace the entire cooling apparatus (heat sinks, heat pipes, and thermal paste), which usually comes as a single "part" from the manufacturer.
To find the right part(s) contact your notebook's manufacturer and ask them to locate you a local repair depot. Contact that repair depot and either get them to fix it, or see if they will be kind enough to order the part for you.