Yeah, that should honestly be enough to get all of it off.
If its more worn in though, I suggest to use some kind of cleaner, but you have to use a special kind of course. It shouldn't be a problem though.
Woh... those temps are worse than mine, and I'm pretty sure my processor would get hotter than yours
...
As for your case fans, by any chance are there any more spaces? Maybe at the front?
Its best to have one side bringing air in, and one side taking air out you see. Otherwise, air just circulates, and I think that is happening with you.
Getting a new fan/heatsink though will help a bit, but if that ambient temperature of the case isn't brought down also, heat will still slowly collect up.
EDIT:
If you do need more removal than a straight cloth and cotton bud, check out this thread which might help:
http://www.computerforums.org/showthread.php?t=39453
I though could get all of it off (at least all non-microscopic parts) just using a cloth.