I agree that it sounds like a name resolution problem.
Although I am not sure what you mean by "when we connect the server to the Internet". Do you mean "when we have our Internet connection UP"?
The scenario is likely: when your network is connected to the Internet, your clients try to find the address of the server "intranet.mycompany.com" using DNS. But they're pointed to the DNS at your ISP which replies right away "I don't know that system". So then your clients fall back to using WINS or whatever, and find the server fairly quickly.
Without the Internet connected, DNS tries but cannot find the DNS server at your ISP. But in the "never say die" way things like this are, it keeps trying for some time. Eventually it gives up, and the clients fall back to WINS.
If this describes what you're experiencing, then there are a couple of approaches you can take.
One is a Registry hack to tell Windoze to try WINS first, then fall back to DNS second (rather than the other wayaround).
The other is to install DNS internally. Tell your Internal DNS to pick up records from your ISPs DNS server(s), and also create a ZONE file to identify the systems on your Intranet. Then point all of your clients to this internal DNS.Hope that helps...