SOAP API – Parsing WSDL Could Not Load from HTTP- 401 Authorization Required

(I believe this question is not quite a duplicate of the other Parsing WSDL questions, as I'm receiving a 401 Authorization Required error)

Every so often on Magento 1.13.1.0 when connecting to my soap API I'll receive the following error

SOAP-ERROR: Parsing WSDL: Couldn't load from 'http://example.com/index.php/api/soap/index/?wsdl=1' : failed to load external entity "http://example.com/index.php/api/soap/index/?wsdl=1"

I dug into the apache error log and pulled this out

[Tue Jan 20 14:12:14 2015] [error] [client 192.168.200.11] PHP Warning:  SoapServer::SoapServer(http://example.com/index.php/api/soap/index/?wsdl=1): failed to open stream: HTTP request failed! HTTP/1.1 401 Authorization Required\r\n in /var/www/vhosts/magesite/lib/Zend/Soap/Server.php on line 762
[Tue Jan 20 14:12:14 2015] [error] [client 192.168.200.11] PHP Warning:  SoapServer::SoapServer(): I/O warning : failed to load external entity "http://example.com/index.php/api/soap/index/?wsdl=1" in /var/www/vhosts/magesite/lib/Zend/Soap/Server.php on line 762
[Tue Jan 20 14:12:14 2015] [error] [client 192.168.200.11] PHP Fatal error:  SOAP-ERROR: Parsing WSDL: Couldn't load from 'http://example.com/index.php/api/soap/index/?wsdl=1' : failed to load external entity "http://example.com/index.php/api/soap/index/?wsdl=1"\n in /var/www/vhosts/magesite/lib/Zend/Soap/Server.php on line 762

The problem is that this error is inconsistent, some times I am able to connect without issue and others I receive this error.

I created the following script to test the issue:

<?php

$url = 'http://example.com/api/soap/?wsdl=1';
echo "\nConnecting to\n$url\n";

for ($i=0; $i<100; $i++) {
    /** @var SoapClient $client */
    $client = new SoapClient($url);
    echo $i."\t";
    try {
        echo $client->login('username', 'key')."\n";
    } catch (SoapFault $e) {
        echo substr($e->getMessage(), 0, 50)."\n";
    }
    unset($client);
}

The output of which looks like:

Connecting to
http://example.com/api/soap/?wsdl=1
0   SOAP-ERROR: Parsing WSDL: Couldn't load from 'http
1   SOAP-ERROR: Parsing WSDL: Couldn't load from 'http
2   aa58f99c61e58e7f2366632886665352
3   SOAP-ERROR: Parsing WSDL: Couldn't load from 'http
4   SOAP-ERROR: Parsing WSDL: Couldn't load from 'http
5   SOAP-ERROR: Parsing WSDL: Couldn't load from 'http
6   SOAP-ERROR: Parsing WSDL: Couldn't load from 'http
7   SOAP-ERROR: Parsing WSDL: Couldn't load from 'http
8   SOAP-ERROR: Parsing WSDL: Couldn't load from 'http

You can see that on run #2 we login successfully, making this a weird intermittent issue.

What is even weirder, is when I enable WSDL cache (System -> Configuration -> Magento Core API -> Enable WSDL Cache) it seems to fix the problem completley. I never receive the error again, and the program output looks like:

Connecting to
http://example.com/api/soap/?wsdl=1
0   4c89a4cb0ccc8d1ed8310067cde6bdaf
1   415bf4a7f89e9df66366c20c081569ef
2   6d339eb604244fe9a6f1df64aebd07ce
3   fa940c6b5561b5d248e0c458e3c68630
4   453c8a33c21404cba98a08c051852ba3
5   01f6a34924b7c7a3d80b2d8b66f6f31e
6   85baa98accdc480fd4cfda41c8ca3f50
7   931fa7574600f22d895fb47233fa91ce
8   72c40849df54d96e4af818a5e1e2ccd3

Can anyone shed any light on the issue, how is WSDL cache supressing this auth error, and what the correct fix might be?