Hi there.
Maybe I shouldn`t post anything here, due to my absolute lack of knowledge when it gets to computers. The "chip" in the brain that allows most people to understand them, in my case sure got lost somewhere between the last two decades last century or simply I was born without it,
, cause each time I must face a new dilema related to the issue, I can spend months trying to figure out how to solve the problem, but many times, thank goodness my son has grown big enough to solve the problem for me.. 
.....whatever.Back to topic :
In my case, I`m still stuck with Windows XP (which is already enough complicated to me, to switch to another more advanced operating system (w7 is too much for the few neurons still left in my head). I can`t say that I know exactly what happened to your computer, but in my case about a year ago, in one of those automatic actualizations, it simply deleted lots of stuff from my computer (games, the calculator and yes, MS paint). I still had the icons, but none of those programs worked and my computer simply couldn`t recognize if they even existed.
After hitting my head lots of times on a wall, and asking for help in the net, some people there told me that this issue was more common than what I thought, that there are pathways where you can insert the missing links in order to have those deleted items back, but in my case, the explanation resulted worse than the original problem, so I did it the old way (suggested by another cro-magnon, like me, related to computers) : I seeked in the net for the original program and downloaded it. The only problem is that there were so many programs called paint, that I had to try lots of them before actually finding one similar to the original program. Some had so many tools, that it would take "some" people a lifetime to understand, but whatever, that`s what I did and now, I`m once again able to to access Paint drawings.
Hope it helps somehow.......
Bye....