Apache 2.4.18 dando aleatoriamente 404 para arquivos existentes

Estou tentando entender por que isso estaria acontecendo. Eu nunca tive problemas neste servidor em torno disso, então estou um pouco confuso.

O servidor é nginx + proxy reverso Apache 2.4. Então nginx eu tenho este proxy pass:

    location ~ \.cgi$ {
        try_files $uri =404;
        gzip off;
        proxy_set_header X-Real-IP  $remote_addr;
        proxy_set_header X-Forwarded-For $remote_addr;
        proxy_set_header Host $host;
        proxy_pass http://127.0.0.1:8181;

    }

Então, para os domínios na configuração do Apache, tenho:

<VirtualHost *:8181>

    # other stuff here

    <Directory "/the/web/directory/*">
        Options +ExecCGI +FollowSymLinks +MultiViews
        AllowOverride AuthConfig
        Require all granted
        AddHandler cgi-script .cgi .pl
    </Directory>

</VirtualHost>

O domínio está habilitado e funcionando normalmente. No entanto, ao desenvolver um site para alguém, me deparei com um erro estranho.

De vez em quando a página dá um 404:

..ainda que o resto do tempo funciona bem. Neste caso, eu estava enviando exatamente os mesmos parâmetros para ele (apenas reenviando o formulário). Verifiquei se o problema é com a solicitação AJAX, mas recebo o mesmo problema se abro a URL em uma guia e pressiono recarregar algumas vezes para testar.

Nada de útil aparece no arquivo de log do Apache:

authorization result of <RequireAny>: granted, referer: https://x.co.uk/contact.html

Estou bastante confiante de que o erro está vindo do final do Apache, pois a resposta para o 404 é:

Not Found

The requested URL /cgi-bin/contact.cgi was not found on this server.
Apache/2.4.18 (Ubuntu) Server at x.co.uk Port 8181

Estou um pouco perdido sobre o que isso pode ser. Alguma ideia?