For others who have a similar problem:
You may have other hardware issues besides the thermal paste issue. You could also be encountering a software issue which I would isolate out first as I often see this as the root issue more often. In this case wiping down the HD proved it was more likely a software issue.
I would start by checking the OS and Apps, make sure you have the latest updates running of your apps and any add-ons. If you have any older OS add-ons they may not play well with the newest versions of OS-X (Snow Leopard or Lion) disable them. Also make sure you don't have applications loading on boot.
If that doesn't solve your issue see if you can boot under an external HD which has a fresh copy of OS on it. If the system does not get hot like before using the external HD apps you can focus on isolating out what is running on your systems internal HD that is chewing up your CPU causing it to over heat.
You could have some Malware running or some background Java applet running inside your web browser. Make sure yo don't have the Flashback Trojan running using this tool from Apple if your running Lion with out Java (http://www.cultofmac.com/160766/apple-re...) Using Apple Software update will take care of older versions of OS-X and Lion that has Java.
To isolate out other malware or other background apps from the OS try creating an new user account on your system. Using this account on your internal HD see if the heat problem persists. If not you have something running in the browser under your original user account. Going into the browser settings fully reset all of it's saved items (Safari > Reset Safari... check off all of the items). Doing this will loose any saved settings so make sure you have written down your web server user accounts and passwords as well as any important URL links. Remove any add-ins and download and instal fresh copies. Lastly, Flash is not well written and does cause excessive heating when watching movies (Hulu) Adobe just released a Beta version of Flash 11.3 that is much better in using the systems resources (http://www.cultofmac.com/160343/adobe-re...)
If the problem is within your OS services you may need to get a good antivirus app to clean out what is running in background (malware trojan software).
I would also at this point defrag the HD as drives that are very full tend to require more effort to access causing heat. You may need to make more free space so less swapping takes place.
If this doesn't solve it you will need to dig deeper into isolating out the different processes running on your system which is a bit of science and luck using Apples 'Activity Monitor' application.
If you really suspect the issue is hardware:
I would start checking for dust and debris issues inside. Check for a clogged fan and vents. Using canned air a small paint brush carefully scrub out the vents, case & logic bd, blow out any dust you do find. You may not have cleaned things out well enough the first time you did this.
Next using 'Check My Temp' application available from the Mac App Store you can monitor the different temp sensors your system has you might be able to isolate out what area of your system is running hotter (don't assume the hottest thing is the issue) HINT: see if a friend who has a similar model can run this app as well to compare against. You may find one of the fans is not working correctly or the HD has issues besides the CPU not cooling because the thermal paste has dried out.