So here's what happened. I took apart the entire thing, and blew out all the dust with some compressed air (Supplied through a gentle air compressor I have, so as to not knock any of the parts loose). I was still hitting pretty high temps. So I just said "screw it", bought a replacement fan and some thermal grease of off Amazon, and completely redid everything. Brand new thermal grease, brand new fan, and completely clean.
I am pleased to report that this machine is now staying cooler than ever, as you can see here http://i.imgur.com/Hzk17sx.jpg
Thank you for the help, everyone. It is much appreciated