Just a final FYI for the guys that were so kind to reply in this thread:
I had resolved to continue putting up with the delays on my modem connection as described above but thought, "I'll give the tech support at my ISP one more try".
I managed to talk to someone who actually had a clue and he diagnosed the problem quickly: The default IP settings for the network adaptor the modem was connected to are "determine IP address automatically". Each time the computer was started the modem was being polled by XP but the connection was getting confused by the presence of the modem, hence the minute long hang.
To solve the problem all I had to do was enter an arbitrary IP address for the network adaptor and now there is no startup delay at all.
