Not having direct access to you computer and having tried everything else . . . I offer one last suggest for you problem, a long shot but . . .
Because you always get the same error . . . since the beginning of the problem and even after a system restore I'm starting to think the keygen may have written to your boot sector. Adobe did something similar with their DRM when CS first came out. If it is loading a driver from the boot sector the system restore may be doing a quick format and leaving the boot sector intact which may be how the driver is avoiding deletion / detection.
The next thing I would try is a full format of the disk with fdisk or another disk format utility. I have several bootable cd's / bootable programs on cd which could do this but . . . you probably don't. It would take lots of time to explain how to create a bootable cd / DVD so I will not attempt to do so. There are partition programs both retail and free that will doing the job as well.
I have never used this but
find tutorials and ISO burning software here if your burning software will not burn a bootable ISO disk. Once you had the bootable disk you would boot to it, use one of the utilities to do a full format and then shut down, boot to your System Restore Disk 1to restore the system.
Downloading the ISO and burning it to a bootable disk is lots of trouble after which you would have to use a program you are unfamiliar with. Seagate, Maxtor and Western Digital all have bootable disks that come with their hard drives for doing the job if you have a friend that has replace a disk lately. Seems I remember WD's disk only worked with WD hard drives though.
Did your System Restore disk offer to do a "full" format? If so and you did the full format (takes a while but it's worth the wait) than disregard all of the above . . . =)