Well the end result, if only (I know, it isn't effecting me) messing with the physical image quality that is saved as you are seeing, then it wouldn't show any sign of virus infection. Which is why I suggested checking some of the files at VT (to basically confirm this) or as I suggested later to view the file with a text editor to see if there is anything say text string to open a and execute a file, etc.
However, I don't think that is likely as that hacking of an image file would certainly ring alarm bells in avast and probably several other AVs. It is this lack of a payload that I find very strange, whilst in the old days (2000) perhaps there were people who only wanted to see just how widely they could spread a piece of malware or announce their so called abilities. Again if that were the case why target paint shop pro with a restricted audience.
So we keep getting back to the how is it determined to be a virus if nothing found it then and nothing finds it now, with none of the usual malware symptoms other than this graphic quality issue (which no doubt makes having that version of PSP worth very little).
So I honestly don't know what else to suggest, perhaps it is time to try a later version of PSP.
System restore is far from perfect and it isn't something I would pin any hopes on as it doesn't monitor all files nor is it a backup tool. I prefer using drive imaging software, that makes and exact copy of the partition, which you can restore.
