OK you say that you know that you don't have a virus so we will assume that this is not the cause. I can understand why some would assume virus after having encounters with Magistrate et al. Just make absolutely sure that you are clean by using a known clean scan disk to check your machine or otherwise check your media without booting from it. I have dealt with anti-virus issues for 13 years and the increasing stealth of some virus types are quite impressive and Norton's and McAfee product are usually targetted for circumvention as they are the major market holders.
I have had icons repeatedly layer themselves over each other and thus appear to be missing on a couple of occassions. Creating a new profile and transferring the data solvedthis both times. You have re-installed Win2k from scratch so that would seem to eliminate a corrupt profile - or maybe not.
You have not indicated whether this is a stand-alone machine or whether you operate in a network environment with roamingprofiles. If you are using roaming profiles then the bottom line may be to back up your data, blow away your network account and stored profile and start from scratch.
If you are on a stand-alone machine are you continually changing display settings from a very high resolution to very low resolutions and back again? This would of course cause a busy desktop to overlay some icons. I know that this is a "Duh" type question that is almost patronising, but we all sometimes overlook the obvious.
I'm sorry I can't offer any more suggestions but my initial suspicions would have been:
1. Corrupt Profile
2. Virus
And from what you have outlined both seem to be eliminated.
Good Luck
