Have a look at the two removal guides below. See which one of the two looks most familiar. The malware responsible causes much of the same symptoms you spoke of. I suspect it may be the first, but see for yourself. If it's neither, let us know.

Remove Windows XP Recovery (Uninstall Guide)

Remove Windows Recovery (Uninstall Guide)

Once determined which FAKE anti-spyware program it is, bypass any ads and go directly to where you see "Automated Removal Instructions using Malwarebytes' Anti-Malware:". Follow ALL the instructions.

The guide also instructs you how to "unhide" the files, you thought were erased. You'll find it below the screenshots for Malwarebytes' Anti-Malware. Along with how to get your desktop background back.

Best of luck..