Служба, которая отправляет запрос, запущена от пользователя Local System, настроить прокси сервер для этой учетной записи не представлялось возможным и я получал ошибку связанную с тем, что клиент не может достучаться до сервиса.

Сначала была предпринята попытка включить прокси для всей системы

и после этого ошибка изменилась на: Удаленный сервер возвратил ошибку: (407) Требуется проверка подлинности посредника (eng. Proxy Authentication Required). 

Затем в коде 

public partial class SOAPServPortTypeClient : System.ServiceModel.ClientBase<SOAPServPortType>, SOAPServPortType
{
     public static SOAPServPortTypeClient Create()
     {
          var client = new SOAPServPortTypeClient();
          client.Open();
          return client;
     }
}

Добавляем credentials

public partial class SOAPServPortTypeClient : System.ServiceModel.ClientBase<SOAPServPortType>, SOAPServPortType
{
     public static SOAPServPortTypeClient Create()
     {
          var client = new SOAPServPortTypeClient();

          System.Net.NetworkCredential creds = new System.Net.NetworkCredential("login", "p@ssword", "domainName");
          client.ClientCredentials.Windows.ClientCredential = creds;
          client.ClientCredentials.Windows.AllowedImpersonationLevel = System.Security.Principal.TokenImpersonationLevel.Delegation;
          client.Open();
          return client;
     }
}

В customBinding добавляем новый биндинг

<binding name="transServiceBinding">
<textMessageEncoding messageVersion="Soap11" />
<httpsTransport maxReceivedMessageSize="20485760" proxyAddress="http://proxy.ru:8080" proxyAuthenticationScheme="Ntlm" useDefaultWebProxy="false" />
</binding>

И прописываем его в клиентском эндпоинте.

После этого достучаться до сервиса удалось!

Затем прокси для всей системы был отключен, и адреса прокси-сервера, прописанного в биндинге хватило для успешной работы с сервисом через прокси-сервер с NTLM-аутентификаций.