.css and .js files only loading when refreshing page after deploy

Whenever I’m deploying updates on our Magento 2 live environment, I run into the issue that on first page load, the .min.css files and sometimes the .js/.min.js files aren’t loading (the browser runs into a 404 when trying to load the files from the server).

However, this only seems to be the case on first load after the deploy. When I then refresh the page, it suddenly finds the requested files (sometimes immediately on first retry, sometimes it takes a few attempts).

Does anyone have an idea why and how to fix this? I’ve tried to think of potential causes, but I’m already running cache:clean and cache:flush and the static signature should be a different one after the deploy.

To summarize some information that may be helpful:

• The servers are running in production mode, I am developing on a dedicated development server and pushing updates with git.
• The command used is setup:static-content:deploy -f
• Our company is using two servers and a load balancer to host the site
• Each server is being deployed individually
• The static files are signed (using a part of the git commit hash so both servers have the same signature)
• It affects both frontend and admin panel

EDIT

Here’s the cache configuration in case this is relevant. Each server runs the static files in its own respective folder; this was changed from a shared static folder recently.

'cache' => [
    'frontend' => [
        'default' => [
            'id_prefix' => 'b1c_',
            'backend' => 'Magento\Framework\Cache\Backend\Redis',
            'backend_options' => [
                'server' => '<SERVER>',
                'database' => '1',
                'port' => '<PORT>',
                'compress_data' => '1',
                'compression_lib' => ''
            ]
        ],
        'page_cache' => [
            'id_prefix' => 'b1c_'
        ]
    ],
    'allow_parallel_generation' => false,
    'graphql' => [
        'id_salt' => '<SALT>'
    ]
],
'cache_types' => [
    'config' => 1,
    'layout' => 1,
    'block_html' => 1,
    'collections' => 1,
    'reflection' => 1,
    'db_ddl' => 1,
    'compiled_config' => 1,
    'eav' => 1,
    'customer_notification' => 1,
    'config_integration' => 1,
    'config_integration_api' => 1,
    'full_page' => 0,
    'config_webservice' => 1,
    'translate' => 1,
    'vertex' => 1,
    'amasty_shopby' => 1,
    'ktype' => 1
],