A while back I had an issue with my laptop wherein it would be running with the fans spun-up for no real reason whatsoever, so I ended up looking around Horsham for some thermal paste, after my semi-annual cleaning of the heatsink proved fruitless. The only thing I could find was some no-name stuff at Jaycar, so I used it.
It improved the temperatures slightly, but it still wasn't right so last week I ordered some decent stuff from PC Case Gear. I ended up going with "Gelid GC-Extreme" because the Arctic Silver stuff I'd always used was considerably more expensive, and in most reviews this stuff wasn't far behind (and it was actually in front on one or two).
Today it arrived, along with an XBox 360 controller for the desktop because the original Dual Shock with a USB adaptor has connection issues. I set about taking my laptop apart, but before I did so I ran Prime95 and watched the temperatures for a bit. I say "a bit" because after about two minutes I stopped the test, with one of the cores reaching almost 100C (!!) and it was pretty clear the throttling on the CPU had kicked in rather aggressively.
So I took it apart, applied the paste, and put it back together. The fan and heatsink is still perfectly clean, so I didn't bother with that. After boot I span up Prime95 again, and after almost 20 minutes the temperatures were just nosing into the 90C area on one or two cores. I'd call that a success, but we'll have to see how it fares in a couple weeks.
Interestingly enough, when I lift the rear of the laptop about a centimeter off the desk, the temperatures drop by at least 5C over the space of about thirty seconds, and will drop further if you give it time.
When I closed Prime95 down, my laptop is quieter than it's been in a long time, so I'm pretty happy at this stage.