moleslayer, this is quite an odd one.
My I sugest that, to help diagnosis, you take a look at the processes that are running immediately after start up when you know that the Dial-up is going to work and then compare the list with the processes that are running when you know that the Dial-up is not going to work.
You'll recall that this list is found by pressing Ctrl/Alt/Del simultaneously. Only do this once and Cancel in between or you'll upset the applecart.