Pastor Dan, I re-read your symptoms and sorry for missing it in the first posting. If your system is completely shutting down and not doing a video lock up, then it is most likely not the GPU. When a GPU overheats, you get anomalies like artifacts first and then your whole video will lock up. I have not yet seen a video card shut a system down as it does not have the ability to tell the motherboard it is overheating. The MB has sensors in various spots on the primary chips like CPU, north-bridge, etc that tell it what the temps are. When those temps hit a threshold, it shuts down to protect itself.
First step is to remove the heat sink from the CPU and do the same thing you did with your GPU. Clean fan, replace old paste, etc. You can also remove the heat-sinks from the other chips and do the same thing. Basically a complete cleaning and paste replacement on all heat-sinks.
If this doesn't work to resolve the issue, then quite honestly the only thing remaining that I can think of that would make a system do a shutdown is the power supply. If your power supply is not functioning properly under load, then it just won't have the power to run your system and the power supply will shutdown.
So since you already have the paste, I would suggest the cleaning of the main chips and see what happens. If it still happens, then power supply replacement may be necessary.
Also, just a suggestion. Get into the habit of blowing the PC out every 2-3 months to get rid of dust bunnies and at least once a year do a complete tear down and cleaning. Replacing the old paste and any worn out fans. This will help keep it in optimal gaming condition.
(which reminds me... I need to clean mine... hope this helps)