Лично я сомневаюсь, что это XDocument. Первое, что я хотел бы сделать, это подключить сетевой инструмент, такой как Fiddler, чтобы увидеть, что произошло по проводам. В частности, мне интересно, если вас душит NLB или что-то подобное.
Если бы там не было ничего очевидного, я бы разбил его на шаги; загрузить как XML (возможно, WebClient DownloadString), а затем проанализировать XML локально. Преимущество здесь в том, что вы можете добавить несколько вариантов try / catch, чтобы в случае неудачи вы записали полученную строку ответа для анализа.
Если вы сделаете это, и он начнет себя вести, то это может указывать на ошибку в XDocument.Load; Точно так же, если вы делаете это, и это терпит неудачу, но все ответы были правильно сформированы в XML, то аналогично - ошибка в Parse. Но это также должно исключать (или определять) связанную с сетью причину.