I work for PA.net as a Mac Tech support and web designer. We've come across six different macs that have this problem of connecting to the internet on startup...one even randomly connected while I was on the phone with the lady. The only solution we ccould find was to re-install the OS. Incidentally, it was happening on OS 9 and 8.6. Nothing is in Startup Items, and on this particular one, I couldn't even disable the "Connect on opening TCP/IP applications" feature...it was grayed out.
All of these situations appear to have started around the same time...about a month ago.
Anyone have any thoughts / similar experiences?