Ok, here are the results of a FurMark test:
After 3 mins: http://img824.imageshack.us/img824/4436/63612001.jpg
At 5 mins, 56 seconds: http://img99.imageshack.us/img99/8828/74721013.jpg
The first one, it froze up only for a moment. Then it continued just fine. At 5:56, it froze for a long time, then went back to normal, then artifacted again at 5:59. At this point I got too worried to let it continue running. As you can see, both Everest and FurMark log GPU temps and it was high in both of them, even Everest which is supposed to be more accurate. After I stopped running Furmark (as I'm writing this post), I still got some artifacting but it wasn't serious, just 'blips' of it and they've mostly gone away now.
Based on these results, would you say the Power Supply is not giving the card enough power, or are certain functions on the card just straight up dying?
Usually if its a power supply issue you would get BSoD or other fatal errors required that you reboot.
You have serious artifacting so I can confirm a GPU malfunction (most likely memory). According on the Everest reading its not the GPU core that is overheating, but most GPUs don't tell you the temperature of the GPU memory. However, it doesn't really matter the GPU memory is defective, overheating or both.
If you have a warranty then get the paper work started for the RMA, if not you'll need to buy another graphics card.