I have had the same issue arising--after downloading the latest version of CCleaner upon my Windows 2000 machine, and, installing it. Immediatel gone were almost...all icons--but, a handful. Then, after a Right-Click upon the Desktop, and, clicking Refresh--I did manage to get...MANY icons back, again. Gone were...dozens, however with ALL (almost) re-arranged in ways different from originally. And, since ALL OF the spacing and most of the locations had changed: maybe, some of them are off-page (somewhere...I don't know)?
Any...(all) "answers", appreciated (I haven't rebooted since this fresh...install--NOR, have I run the latest version...installed; only installing it).