Web Service Request failure Recovery time

Question

I have C# application that consumes a web service. The problem I have is that if a request fails because the service is unavailable, I get weird behavior when attempting future requests when I know the service is available.

Example Sequence of events:
1. Application is started with service unavailable.
2. Request[1] is made to test availability.
3. Request[1] fails.
4. Service is made available.
5. Request[2] is made to test availability.
6. Request[2] fails.
7. Subsequent requests fail until approx. 60 seconds has elapsed since Request[2].
8. Requests from this point on succeed.

It seems to make no difference how much time elapses between steps 4 and 5, and it doesn't seem to matter when service availability changes (can start with service available, make successful requests, then disconnect and start above sequence with same result.)

It appears that there is some timeout that must elapse before the request is re-issued to the server, but I would think this timeout would start after failure of Request[1], so if I wait long enough after the service becomes available again, the first request will succeed... but this doesn't appear to be the case.

Any insights would be appreciated. I would like to be able to adjust whatever timeout value is being used, so that I can reconnect more quickly if there is a drop in service.

As for implementation, it is fairly straightforward. I added my service as a web service reference, and use code like the following to make requests (generic code example).

public string MakeRequest(args)
{
    using (MyWebService service = new MyWebService())
    {
         service.Url = myServiceUrl;
         return service.MyWebServiceRequest(args);     
    }
}

A couple of other notes:

1. I do not have control over the web service I am consuming.
2. In this specific case, availability means I am connected to the VPN where this service is available. However I think I would see this problem if it was any general connectivity issue.

Thanks!

Update:
I have played with all of the timeout values I can find and none seem to affect it. Any ideas would be appreciated.