Если на клиенте стоит прокси, то попытка вызова веб-сервиса вызовет исключение ProtocolException, которое сообщит об ошибке HTTP Error 407 Proxy authentication required. Порывшись в интернете, нашел решение:

Способ №1

var networkCredentials = new NetworkCredential
{
    UserName = "<your username>",
    Password = "<your password>"
};

var webproxy = new WebProxy(new Uri("http://<address>:<port>").ToString(), true, null)
{
    Credentials = networkCredentials,
    BypassProxyOnLocal = false
};

WebRequest.DefaultWebProxy = webproxy;

После установки DefaultWebProxy у класса WebRequest можно создавать клиенты и делать запросы к веб-сервисам.

Способ №2

Нужно заставить System.Net использовать прокси по умолчанию.

<configuration>
    <system.net>
        <defaultProxy useDefaultCredentials="true" />
    </system.net>
</configuration>