Unfortunately, replacing power supply did not help. The shutdowns kept getting more and more frequent. Since there is no new Mac Mini's from apple, I am experimenting with a hackintosh, based on an Intel NUC.
The hatch is prone to failure. In my case it was the digital lines of the video port - analog VGA worked fine. I think you should try replacing the hatch.
I had this problem for a long time. In general smcFanControl software helps. It let's you speed up the fans to a point when the GPU is no longer overheating and the artifacts and freezes no longer happen.
This guide does not say anything about thermal paste. For the original Mac Book Air model, that requires the fan to be replaced together with the heatsink, the thermal paste should probably be removed and re-applied. Here's a guide on how to do it.