InternetOpenURL hangs a long time and fails first call. Subsequent calls work. What's going on?

Question

Pretty simple code:

        char* gAgent="[My program agent]";
        gInternet=InternetOpen(gAgent,INTERNET_OPEN_TYPE_DIRECT,NULL,NULL,0);

        DWORD aFlags = INTERNET_FLAG_NO_UI|INTERNET_FLAG_PRAGMA_NOCACHE|INTERNET_FLAG_NO_CACHE_WRITE;
        if (strstr(theURL,"https:")) aFlags|=INTERNET_FLAG_SECURE;
        else aFlags|=INTERNET_FLAG_NO_AUTH;

        HINTERNET aURLHandle=InternetOpenUrl(gInternet,theURL,NULL,0,aFlags,NULL);

Here's the strange behavior: The first time I run this program (since starting Windows), it will hang a long time on InternetOpenUrl and fail. All subsequent calls succeed. Even stranger, all subsequent calls in OTHER programs using the same code library will do the same behavior. It looks like the first time I call InternetOpenURL in any program since starting windows, I get some kind of long (handshaking?) wait that fails. Then it succeeds.

Can anyone explain this behavior?

(Even if I simplify the code to just be...

HINTERNET aURLHandle=InternetOpenUrlA(gInternet,theURL, NULL, 0, INTERNET_FLAG_RELOAD, 0);

...I get the same behavior)