Just to see if it would help....have you done a system restore just to get them working again? From there do individual installs of all recently added programs and updates.
Try this out as well if you have not already... Taskbar Repair Tool Plus!
The information is from an article posted here...Systray icons missing | Windows Problem Solver
they have this explanation that seems to fit very well as the culprit.
"Main problem and complete solution
The main cause of the more common problem is that the systray program is temporarily unable to process icon inclusion requests. An earlier hypothesis, that systray.exe is loaded too late, has been refuted by Thomas Gregory Platt (see his email below).
According to the excellent analysis in the Problem analysis and proposed solution comment by tasmanian this is caused by a timing defect in the Windows function Shell_NotifyIcon in shell32.dll, which has a timeout fixed at 4 seconds. Combined with an unfavorable Windows API message this causes the problem, which befalls many heavily loaded computers that don't have ultra-fast hard disks. Changing the timeout to one minute and removing the unwanted message solves the problem, and in the Complete solution comment user depassp has perfected the procedure of patching shell32.dll to solve the problem, at least until a new version of that DLL is delivered by Microsoft that re-introduces the problem and requires another patch session. In fact, exactly this has happened around July 2010, but the solution is already here: Offsets for NEW 6.0.2900.6018 file by mcrealize, corrected by TeaRex
Unfortunately patching a system DLL is not an entirely simple procedure and can only be done with a certain minimum of computer handling experience, but this is the best we can offer for now.
2010-10-09 – nars has posted a patcher tool (direct download link) that promises to solve the problem even for future versions and to make the patching even easier."