I tried using SoftFSB on a few laptops, and I wasn't able to get it to work. it would instantly carsh the computer. However, SoftFSB has support for certain IBM thinkpad laptops, so it is possible.
I don't think heat will be too much of a problem for small overclocks. At least I think that an 800 Mhz laptop has the same cooling as a 700 MHz laptop.