Have you used Task Manager to make sure the startup
programs aren't actually running. I bet they are still loading
but their icons are not being displayed in the notification area.
Normally this can happen if Windows Explorer crashes
and restarts itself. However, that doesn't seem to be
your problem. Have you checked to see what icons
are "Hidden" and what's set to "Always Hide"?
This can be a perplexing issue. I've had this happen twice.
Never on Vista, though.
There are different procedures that might fix this.