Applications Don’t See Internet

I have a multiple user computer with XP PRO. When one user has finished using the system and signs off, the next user finds the following problem;

Upon signing in they can connect to the internet but every other application will fail to see the internet. Outlook will generate an error that it cannot find the server, EI cannot find a page, and no favourites link at all.
It often takes several reboots of the computer before the problem is resolved.

What can be done to eliminate this aggravation?