Why is my laptop overheating and shutting down randomly?

The temperatures on my Macbook Air get pretty hot (80 degrees Celsius +) at mid-heavy use, like streaming videos online or opening iPhoto, causing the fan to run at 4000~5000rpm. When hot, the laptop will also shut down when I lift it up from a surface.

After doing SMC resets and running hardware diagnostic tests (which all of the components of my laptop passed, no problem!), I'm beginning to suspect that the thermal paste and heat sink needs replacing. Someone else I talked to suspects that I need to replace the fan. I would just like to be a bit more confident about which part to replace before taking my laptop apart (that is, if this is something I should be doing.) Does anyone have any idea?

I'm resorting to this because the previous two Genius Bar experiences I've had concerning this issue have been largely unhelpful; the first guy just dusted out the fan, the second guy told me that I had to replace the logic board entirely!