LocationCriterionService lookup causes DEADLINE_EXCEEDED

<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<soapenv:Envelope xmlns:soapenv="http://schemas.xmlsoap.org/soap/envelope/" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
<soapenv:Header>
<ns1:RequestHeader xmlns:ns1="https://adwords.google.com/api/adwords/cm/v201509" soapenv:mustUnderstand="0">
<ns1:clientCustomerId>*********</ns1:clientCustomerId>
<ns1:developerToken>**************</ns1:developerToken>
<ns1:userAgent>Natpal-AdStation/1.0 (AwApi-Java, AdWords-Axis/2.7.0, Common-Java/2.7.0, Axis/1.4, Java/1.6.0_45, jars)</ns1:userAgent>
<ns1:validateOnly>false</ns1:validateOnly>
<ns1:partialFailure>false</ns1:partialFailure>
</ns1:RequestHeader>
</soapenv:Header>
<soapenv:Body>
<get xmlns="https://adwords.google.com/api/adwords/cm/v201509">
<selector>
<fields>Id</fields>
<fields>LocationName</fields>
<fields>DisplayType</fields>
<fields>ParentLocations</fields>
<predicates>
<field>LocationName</field>
<operator>IN</operator>
<values>18109</values>
<values>19380</values>
<values>18106</values>
<values>19383</values>
<values>19382</values>
<values>19508</values>
<values>18015</values>
<values>19601</values>
<values>18016</values>
<values>19008</values>
<values>18017</values>
<values>19605</values>
<values>18018</values>
<values>19604</values>
<values>19041</values>
<values>19602</values>
<values>19002</values>
<values>19609</values>
<values>19608</values>
<values>19063</values>
<values>19607</values>
<values>19606</values>
<values>18101</values>
<values>18104</values>
<values>18102</values>
</predicates>
</selector>
</get>
</soapenv:Body>
</soapenv:Envelope>
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<soap:Envelope xmlns:soap="http://schemas.xmlsoap.org/soap/envelope/">
<soap:Header>
<ResponseHeader xmlns="https://adwords.google.com/api/adwords/cm/v201509">
<requestId>00052c9a5e831d300a8165822f05bfc9</requestId>
<serviceName>LocationCriterionService</serviceName>
<methodName>get</methodName>
<operations>1</operations>
<responseTime>534</responseTime>
</ResponseHeader>
</soap:Header>
<soap:Body>
<soap:Fault>
<faultcode>soap:Server</faultcode>
<faultstring>[InternalApiError.DEADLINE_EXCEEDED @ ]</faultstring>
<detail>
<ApiExceptionFault xmlns="https://adwords.google.com/api/adwords/cm/v201509">
<message>[InternalApiError.DEADLINE_EXCEEDED @ ]</message>
<ApplicationException.Type>ApiException</ApplicationException.Type>
<errors xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:type="InternalApiError">
<fieldPath/>
<trigger/>
<errorString>InternalApiError.DEADLINE_EXCEEDED</errorString>
<ApiError.Type>InternalApiError</ApiError.Type>
<reason>UNKNOWN</reason>
</errors>
</ApiExceptionFault>
</detail>
</soap:Fault>
</soap:Body>
</soap:Envelope>

We are getting a DEADLINE_EXCEEDED error trying to lookup (zip code) locations using the AdWords LocationCriterionService.

At first, it seemed like something harmless and we should just retry again in a few minutes and I even found this error listed on the AdWords site:
https://support.google.com/adwords/editor/answer/1106420?hl=en
...but the retries do not seem to be succeeding.

Can you give an explanation for what is happening here?

Files are attached.

--
--
=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~
Also find us on our blog and Google+:
https://googleadsdeveloper.blogspot.com/
https://plus.google.com/+GoogleAdsDevelopers/posts
=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~
 
You received this message because you are subscribed to the Google
Groups "AdWords API Forum" group.
To post to this group, send email to adwords-api@googlegroups.com
To unsubscribe from this group, send email to
adwords-api+unsubscribe@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/adwords-api?hl=en
---
You received this message because you are subscribed to the Google Groups "AdWords API Forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to adwords-api+unsubscribe@googlegroups.com.
Visit this group at https://groups.google.com/group/adwords-api.
To view this discussion on the web visit https://groups.google.com/d/msgid/adwords-api/a5d34382-0d77-449b-a06b-64880c84a152%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.