Sometimes canned air is not enough to clear all the dust out. It may require disassmebly. There are quite a few things that can cause these overheating issues. The heat sync itself can fail, there is a liquid inside of these and it can leak out, if this happens heat will no longer transfer to the cooling fins and the heat sync will not work correctly.
Heat syncs can losen up and stop making a connection.
Because the fan is speeding up and then the computer shuts down, I am quite certain this is a heat related issue. If you have the capability of taking the computer apart, it would be worth re-pasting the heat sync to the chips. This sometimes requires a full disassembly of the laptop. If you can not do this, I would recommend taking the computer in to have it serviced.
Over heating can permanently damage the system. I would not recommend continued use in the current state.
Edited by zingo156, 13 May 2014 - 01:14 PM.