How on earth did Anydvd show up installed?

If you are referring to an image made by Norton Ghost , Acronis Tru Image, or Power Quest's (now Symantec) Drive Image, that's impossible for AnyDVD to appear if it was never on the original image. You may have your dates crossed up when that image was made.

When you restore an image it's like reformatting you drive, what you put on that image is exactly what you get when you restore, nothing less, nothing more.
I have made over 200 image restores with Acronis Tru Image and AnyDVD, or any other program for that matter, never appeared if it did not exist on the saved image.

When you say you restored an image, did you use System Restore from Windows XP?
System Restore is really only a registry and system driver back-up system (not an image system).

System Restore does not actually delete data on a disk that has been put on the disk since the last restore (although it might rename directories). Under some circumstances a later installed application may appear to be still installed.

However, the registry entries may be deleted which for some programs may not allow the program to function correctly. Worse still, it can be difficult to properly uninstall the program. Sometimes though, the application may still run ok.

I agree with itzbinnice if you used a proper image backup program, this could not happen.

Oilman,
You probably are right, he used sytem restore, that's the only explanation.
By using the term image, he threw me off. System Restore does not restore an image, but rather registry settings. Mine is turned off, I find it quite useless and prefer using images.

It was an expired trial version,
I popped in my key and
downloaded a new one.
Thanks for the comments.