If it's just cleaning then you shouldn't need thermal paste. That's for taking the heatsink off.
Then I'm going off to clean it! Will update if it worked or not. Hopefully it will... I don't wanna send it in right now, Diablo 3 is so close and I don't wanna miss playing at release!