While I somewhat agree with the other respondents, if you have cleaned your fan a month ago, cleaning it again will not help. It does sound like a heat problem, but that can be verified very quickly with Nvidia System Monitor, a free tool provided by Nvidia : http://www.nvidia.com/object/nvidia-system-tools-6.08-driver.html
Make sure you grab the correct 64-bit or 32-bit driver, depending on what OS you have installed.
In my experience, overheating does not cause game slowdown. The game will suddenly crash if your GPU gets too hot, with the screen usually putting up random garbage and the sound getting stuck on one (usually annoying) tone. I would be more inclined to search for malware or other junk which is using up all your CPU cycles.
Download and run MalwareByte's Anti-Malware. You can run the free version. Then also run SuperAntiSpyware, also the free version. Between the 2 of them, they will detect most malware. There are more powerful tools out there, such as HijackThis, but they will require some help to interpret the results.
Next go to Start - Run - msconfig, move to the Startup tab, and see if you have any unnecessary crap starting up. You may have to look up each item if you don't know what it is, but you can improve performance quite a bit getting rid of useless items such as browser toolbars, or BHOs (browser helper objects).
After all that, see if you still have game lag.