Laptop P4 3.0 Ghz CPU Temperatures too High or Not?

75 °C is FAR too hot for a desktop Pentium-IV (the thermal specification is 69 °C for a 3.0GHz part), but is well within the specification for a Pentium-M (which has a thermal specification of 100 °C).     The Lenovo overview for the G40 does not indicate whether or not the Pentium is a Pentium-M or a standard (non-mobile) Pentium [see http://www-307.ibm.com/pc/support/site.wss/document.do?sitestyle=lenovo&lndocid=MIGR-50572 ] ... so I can't say with certainty whether or not the temps you're seeing are worrisome.   The idle temp is fine ... but the full-load temp is definitely high if it's a standard Pentium.   However, laptops DO tend to run hot under full load --> that's one reason Intel has "speedstep", "M-" versions of their CPU's, etc. .... to try and alleviate the problems that the small laptop form factors present in cooling the CPU.

If the "normal" temps are consistently under 60 °C I wouldn't be too concerned.   The Pentiums have built-in thermal protection ... and will simply shut down if the CPU gets REALLY hot (you won't, of course, get any message if this occurs ... it will simply shut itself down).

check it out here :
http://www.heatsink-guide.com/content.php?content=maxtemp.shtml

Way of applying doesn't make a difference. They suggest this method so that people don't use thermal compound like toothpastes and apply it all over the cpu.
I recommend the thin film method but the film has to be very thin.

Don't remove the heatsink after applying paste and seating the CPU.
Seat the CPU first, apply compund, and then install the heatsink. Also make sure heatsink is tight.
Sit back and watch temps fall.
NOTE: Arctic Silver 5 takes around 200 hours of intense CPU usage in order to settle properly. Only after around 200 hours will it show its real potential.

If nothing helps, try using some sort of utility to reduce you CPU voltage and frequency, so that your CPU stays cool when not required much. That'll help increase battery life too.

A small fluctuation during idle isn't unusual.   It's not usual to not have a "square mark" of residue ... the thermal compound is supposed to migrate into the areas where there are microscopic variations in the metal; so it's not always an exact rectangle (although a completely uncovered area is definitely not right).   That's why Artic Silver specifies a specific method of applying their compound ... depending on the specific type of processor you're applying it to.   The idea is to get "enough" in the right areas ... and let the pressure between the heatsink and CPU, together with the heat from the CPU, cause it to flow into the appropriate microscopic crevices [that flow, and the bonding that occurs as a result, is the reason the performance of Artic Silver 5 improves for the first 100-200 hours of use].

In any event, it sounds like you've got a much better thermal bond now;  so unless your high-load temperatures are still above 70°C I would consider that all is well.

>>   something that was causing the heat sink to be held up on one side  <<  probably it was not installed correctly, and seated only on one side, and this was the real cause, not the paste.
If it is not flush against the whole surface, it nearly cannot transfer the heat from the cpu to the sink