History? When did icons last appear on desktop, and what's happened since (hardware/software changes, settings change, virus, major crash etc).
Have you tried restoring a version of the registry from before this happened? (boot to command prompt and run scanreg /restore).