Can't say im a NVidia expert, only ever owned a 6600Gt and a 7800GTX back in the day, but the obvious things are reinstall all drivers, set everything to stock (all overclocks) any custom bios's reset to stock etc, make sure all cooling is fine (aslong as your gpu isn't more than 80c dur in games etc), if its still the same, then it looks more than likely that its dying.
I had the same but worse a lot worse, (random lock ups, screen going dead, bsod, graphics card fans going full pelt as if the gpu was at 100c in its head and no signal to monitor etc) kinda thing happen on my HD4870x2 but after using it for 3 years and well, pretty much torturing it, it handled it all for 2 years soild overclocking, then funnily enough, the last year of its life, wasn't playing games much, ran it at stock for a year, then it decided to die on me, though I did actually try the oven bake trick, I thought as it was dead was no harm in it right? I took all the gpu heat sinks off, all the pcb shields, anything that is there that can be unscrewed or taken off or anything that can melt, get a baking tray, make 4 tin foil balls, support each 4 corners with them and make sure they don't touch anything important that they aint supposed to touch, pre heat your oven to 200C spot on, and place your graphics card in for Exactly, 8 mins, maximum, minimum 7 mins, anything less than 7 mins from air temperature of a room, the soldering of the card wont melt back into the correct place, anything more than 8 mins, you could damage stuff you didn't want to do, though with that said, this did fix my 4870x2, on my second oven bake after it died again about 2 months later, it did take about 8 and half mins to fix.
but this is only worth doing if you feel that theres no other way of fixing it, and really aren't bothered if you want to just spend money on a new one, or want to try fix it for noting kinda thing
but if you still have manufacturers warranty, ignore all of above and RMA
Edit: btw, I got another 7 months outta my old 4870x2 and it worked fine even with the full overclocks I used to run it at, though with that said like I said, it died again after 2 months, then I re-baked it, lasted about a month and a half, then died, then about a month, then died, then 4 weeks then died, then in the end up got down to about every 15 days or so of use it died, but etleast it gave me 7 months of use, NVidia cards might last longer after a bake, the results are a lot different, some cards can last up to a few years again after baking, some, not even as long as mine did, but again I must insist that you check any possibilities of drivers etc, that could be causing the issues first, and if you are sure 100% that it is dying, then go ahead and try this, if you feel that you haven't lost anything by trying this
and be sure to re-apply thermal paste etc and the obvious bits and bats when reinstalling the gpu cooler.
Edit2: first video I clicked on, came up with the exact sort of thing that was happening with my card on boot, but I had worse, but just shows the kinda fix that's possible with this trick
http://www.youtube.com/watch?v=Hf3yMzmgT90
