Remote Run times out while fetching suitable configurations

On one of our servers, Remote Run does not seem to work at all, as the server times out when it's asked to fetch suitable configs by a Remote Run plugin:

> The server "..." did not respond within timeout(300 sec)

When I inspect the traffic, I see a response from the server after only 120 seconds, but it's not the response the plugin is likely expecting:

> java.lang.RuntimeException: Failed to acquire suitable configurations lock in 120 seconds

We have over 4000 VCS configurations, some of which may be pointing to servers that no longer exist. Despite this, we still expect this functionality to work as intended.

Your assistance is appreciated.