My CPU is on fire!

My computer is having severe overheating issues.  As soon as I turn on my computer, the fans kicks into high gear and runs and runs and runs.  Still, the CPU temperature goes up and up and up.  At about 50 C, everything slows down in a last attempt to cool itself down.  At 70C it gives up and shuts down.  I have replaced the thermal grease and cleaned the thermal cooling unit (multiple times).  Still, the temperature climbs.  I am not sure what else to do.  Any suggestions?  I am thinking about getting a cooling pad thing to run under it, anyone know of any good-but-still-reasonably-priced ones?