Hello, Did you check in C:WINDOWSsystem32 for mspaint.exe? It may be that the shortcut to the program was deleted accidently, but the program may still be there.
From: http://compeds.com/generalwindowstips.htm "If you don't find the program files, try installing the programs from Control Panel | Add/Remove Programs. Select Windows Components, Accessories and Utilities, and then Accessories. If the boxes for Calculator and Paint are checked, try unchecking to remove them, then going through the process again and checking the boxes to reinstall."