EXACT same thing happened to mine, 3 visits to the Apple Store later until someone finally opened it up completely and dusted the insides. The computer is running like new again. At home dusting without opening it up didn't work.

MAKE SURE THEY DUST THE INSIDES. They do it for free, even if you don't have AppleCare anymore.