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.