Sometimes when i boot my Windows (XP Pro), some applications in the start-up fail to show themselves in the system tray. Yet they are still running in the background. I am so annoyed by this, to get around this problem I have to restart my PC again. It works sometimes and sometimes it don't.
Try logging off and back on again (equivalent to you rebooting, I guess).
Wait before logging in.
Disable any automatic log-on (equivalent to "wait", really).
Check the icons are not hidden(You've already confirmed this is done)
Disable Universal Plug and Play (UPnP) services
(This may work, but might stop you using some devices on your networ that rely on UPnP)
Hide UPnP devices in network places
Set the SSDP and UPnP services to start mode "Automatic" instead of "Manual".
Use a Startup Manager
(Requires additional software to be installed, but will stagger the start up time for the software and may help.)
Is the "Hide inactive icons" option on the Taskbar and Start Menu Properties dialog checked?
Right click over the task bar and select Properties. Go to the Taskbar tab and in the "Notification area" group box clear the option.
I realise that this might seem obvious - but I've overlooked this on a number of occasions.
Perhaps the icons are only hidden?