When you cleaned the exhaust, did you disassemble it and physically clean it (my recommendation here) or blow compressed air through the vents? The design of laptops gives no where for dislodged dust bunnies to go so they simply come right back which is why I suggest opening and physically cleaning the laptop (the only way to ensure all dust is cleared).
This video may be of help
https://www.youtube.com/watch?v=G2AcFvd9qjc
If you did disassemble the laptop and are still having heat issues, you'll want to look into replacing the thermal compound on the heatsink and possibly any thermal pads used (although thermal pads can be reused if one is careful with them)