One of our machines had the same problem. It finally got to where nothing showed in the system tray except McAfee and the clock. I searched the internet high and low for an answer. I searched Microsoft and tried a few "sure to work" solutions that were posted here and there. I tried uninstalling most of the software and reinstalling it. I tried for months to fix it and nothing I did ever seemed to work. Like you, everything (sound, network, etc...) was functioning. I just couln't SEE that they were functioning like I used to be able to. Even the Outlook 2003 systray icon wouldn't appear when Outlook was running and especially the one that notifies you that there's new mail wouldn't appear. The worst part though of the whole thing was not being able to eject the darned thumb drive without going through the back door and jumping through hoops to do it. What a PITA! Too many clicks to find how to eject it and could never remember where heck it was at.
After months of searching for an answer, I finally just wiped the machine and started over, after copying what I needed off of it, of course. ;)
Since then, it has been completely restored to where it was at right before I wiped it, except the icons are all there now. The same software is installed and using the same data files. Same patches have been applied everywhere (Microsoft, Adobe, Java, etc...). Same add-ins are in IE (flash, etc...) and everywhere else I could look. And, the problem has NOT returned.
Just out of curiosity, did yours start doing it shortly after an overnight, unapproved update from Microsoft? Yeah, the stealth updates! With ours, we came in one morning and found the computer had been rebooted after a so called "update" had been applied and the machine auto-restarted. You know the kind... the ones that come while you're not looking even though you have updates set to simply notify you of their availability and NOT auto download/install? Yeah, after one of THOSE, our troubles began. :(
