This is just a theory, so if anyone knows whether or not this is possible, please let me know...
Ah, right- Brazinha
did say that the problem occurs at startup (a key point, and one which I missed before), so what you suggest could be exactly what's going on.
If you've got a lot of programs firing off auto-start components at bootup, it can take a loooong time for everything to initialize, even if you can't
see anything going on. For example, I have definitely noticed a very marked increase in the time it takes a system to "settle down" after installing both McAfee's Security packages on some systems (Norton's equivalent package is no start-up speed demon either). Those two products definitely
do connect to the Internet to do their auto-update thing, and other programs (which you may not even know you have running) will do the same.
There's not much you can do about it if it's something like Norton or McAfee causing the delay; you need those programs, so you just have to deal with it. What you probably
don't need though, is programs like Quicktime or RealPlayer running their auto-start components; you can often shave some time off the start-up process by not having such programs set to automatically start when Windows starts.