Isso ocorre porque o log de acesso está escrito no end da solicitação, não no começo. Portanto, se você fizer a solicitação às 12:00 e levar um minuto para ser concluído, a entrada não será gravada até as 12:01. O fato de poder incluir coisas como o número de bytes transferidos é um indicador seguro disso.
Você também pode executar um traceroute de um host para o outro para ver se ele realmente está obtendo o pedido - se você está vendo atrasos durante o roteamento, você tem a origem do seu problema.