Have you checked to see that your primary DNS server is correct? I've seen weird behavior like this when the primary server is wrong or down and it rolls to the secondary -- often the first requests would time-out and fail, but a second request would succeed.