Microsoft Graph HTTP calls error out with 401 'Access token not yet valid'

I am hitting an access-denied issue calling Microsoft Graph: about 25% of calls fail with 'Access token not yet valid'. My understanding is that there is a clock drift issue somewhere, but I am not sure how to fix that: I just call ADAL.NET to get JWTs as usual. Any idea how to resolve that issue?

Error:

Microsoft Graph error 401 (Unauthorized) calling https://graph.microsoft.com/beta/users?$filter=accountEnabled+eq+true+and+(onPremisesSyncEnabled+eq+true+or+userType+eq+'Member')+and+startswith(mailNickname%2c+'c')&$select=id%2cuserType%2cdisplayName%2cgivenName%2csurname%2cuserPrincipalName%2cmailNickname%2conPremisesExtensionAttributes%2cjobTitle%2conPremisesImmutableId%2cofficeLocation&$top=999&$skiptoken=X'44537074090000000000000000000014000000181CE5FC0A54524E9829853270D390A004000000000000000000000000000017312E322E3834302E3131333535362E312E342E323333310200000000000176B88C34590AE141931E8AE5E73B7EB5'.
{
 "error": {
 "code": "InvalidAuthenticationToken",
 "message": "Access token not yet valid.",
 "innerError": {
   "request-id": "1e2ce0f6-6b3f-412f-9d1b-9ba03e7827a3",
   "date": "2018-04-16T20:20:13"
  }
 }
}

Code:

var accessToken = (await Common.Adal.AcquireTokenAsync("https://graph.microsoft.com", new ClientAssertionCertificate(clientId.ToString(), Secret.ClientCertificate), /*sendX5c*/true)).AccessToken;

var request = new HttpRequestMessage(HttpMethod.Get, url);
request.Headers.Authorization = new AuthenticationHeaderValue("Bearer", accessToken);
request.Headers.Accept.Add(new MediaTypeWithQualityHeaderValue("application/json"));

var response = await HttpClient.SendAsync(request);
if (!response.IsSuccessStatusCode)
{
    throw new OrchestratorException(
        response.StatusCode,
        $"Microsoft Graph error {(int)response.StatusCode} ({response.ReasonPhrase}) calling {request.RequestUri}. " +
        (response.Content != null ? await response.Content.ReadAsStringAsync() : ""));
}