I'm idling at 53/30c (70c max under load) with my BFG 6800GT OC right now. That's with a Zalman 700CU and AS5 though. With the stock cooler I got ~60c idle.
That isn't unusual for that card, but if you're saying it's idling at 63 and only hitting 73 max is that temp after alt+tabbing back to the desktop to check the temp or is it from a log while you're playing? If you are alt+tabbing back to windows it's quite probable that you're hitting 80c or higher in games. The temp drops very quickly as soon as you come out of 3d mode.
I'm just asking because I know my card doesn't like sitting around 80c. I don't get anything as major as your artifacts and weirdness, but I do get some artifacts if I sit ~80c for too long. Either way though, if you're getting artifacts that bad, it looks like it's RMA time.
Blue numers are my temps (GPU | Ambient | CPU)...