Lots of possible causes obviously – DNS, routing, firewall, an issue with their server or app, or an issue with your server or app.
One possible issue on their end that you could easily identify – if they’re using round-robin DNS queries for the api hostname, maybe one of the api endpoints is broken and your request fails when it hits that endpoint. This problem is not uncommon and is fairly easy to identify. For a smaller service, they probably use just one IP for all requests and this is less likely an issue.
Can you reproduce failures outside of WP/PHP? Create a simple, non-PHP, command line script that logs the output and total time of a DNS query for the api server hostname, plus the output and total time of a simple GET request to the api via curl (linux cli curl – not PHP curl) or wget. Run it a few times – does it work? Run it frequently from cron – does it also fail occasionally? Do those failures coincide with the times wordpress’ requests also fail?
Additionally, it may be helpful to log PHP curl verbose output. Maybe try copying the function WP_Http_Curl::request
https://developer.wordpress.org/reference/classes/wp_http_curl/request/
to functions.php as request_debug(). Within that function, enable CURLOPT_VERBOSE and use CURLOPT_STDERR to capture that output as described here https://stackoverflow.com/questions/3757071/php-debugging-curl
Use request_debug() in your plugin and see what it captures.
HTH