Lo sentimos, la respuesta se encontró al escribir

Estoy tratando de conectarme a un servicio web externo que requiere autenticación de nombre de usuario / contraseña a través de un proxy. Estoy usando Visual Studio Express 2008 para generar una referencia de servicio

Me he conectado al mismo servicio web utilizando una referencia web. Solo tuvimos que establecer un tiempo de espera mayor porque tarda mucho en terminar.Me he conectado a otro servicio web que no requiere autenticación de nombre de usuario / contraseña con una referencia de servicio generada y algunas configuraciones para obtenerlo a través del proxy.

Entonces, mi pensamiento sería tomar esta referencia, señalarla al servicio web correcto y agregar autenticación.

La configuración que estoy usando sin seguridad:

    <?xml version="1.0" encoding="utf-8" ?>
    <configuration>
      <system.net>
        <defaultProxy useDefaultCredentials="true">
          <proxy bypassonlocal="False" proxyaddress="http://***.***.****:80" />
        </defaultProxy>
      </system.net>
        <system.serviceModel>
          <bindings>
            <customBinding>
              <binding name="AreaWebServiceSoap12">
                <textMessageEncoding maxReadPoolSize="64" maxWritePoolSize="16"
                    messageVersion="Soap12" writeEncoding="utf-8">
                  <readerQuotas maxDepth="32" maxStringContentLength="8192" maxArrayLength="16384"
                      maxBytesPerRead="4096" maxNameTableCharCount="16384" />
                </textMessageEncoding>            
                <httpTransport manualAddressing="false" maxBufferPoolSize="524288"
                    maxReceivedMessageSize="65536" allowCookies="false" authenticationScheme="Anonymous"
                    bypassProxyOnLocal="false" hostNameComparisonMode="StrongWildcard"
                    keepAliveEnabled="true" maxBufferSize="65536" proxyAuthenticationScheme="Anonymous"
                    realm="" transferMode="Buffered" unsafeConnectionNtlmAuthentication="false"
                    useDefaultWebProxy="true" />            
              </binding>
            </customBinding>
          </bindings>
          <client>
            <endpoint address="http://www.****.*****.****.com/samplewebservice/service.asmx"
                    binding="customBinding" bindingConfiguration="AreaWebServiceSoap12"
                    contract="ServiceReference1.ServiceSoap" name="ServiceSoap" />
            </client>
        </system.serviceModel>
    </configuration>

He agregado el siguiente código a mi llamada de autenticación:

static void Main(string[] args)
{
  ServiceSoapClient s = new ServiceSoapClient();
  s.ClientCredentials.UserName.UserName = @"username";
  s.ClientCredentials.UserName.Password = @"password";

  Service.RawGpsData[] result = s.GetRawGpsData(0);
  Console.WriteLine(String.Format("done:{0}",result.Length));
  Console.ReadLine();
}

Solo usando esta configuración da un error como se esperaba:

La solicitud HTTP no está autorizada con el esquema de autenticación del cliente Anónimo. Se recibe el encabezado de autenticación del servidor, es NTLM.

Ahora me pierdo y empiezo a probar cosas tontas porque estoy empezando a usar WCF.

Cuando agrego la siguiente sección a la configuración

 <security authenticationMode="UserNameOverTransport"></security>

Obtuve el siguiente error:

El enlace CustomBinding.http: / / tempuri.org / para el contrato AreaWebServiceSoap.AreaWebServices está configurado con un modo de verificación para el que se requiere un nivel de transporte con integridad y confidencialidad. El transporte no puede proporcionar integridad y confidencialidad.

Lo siento, mientras escribía esta pregunta me topé con la respuesta. Todavía creo que la gente podría estar interesada en esto y todos los comentarios y pensamientos son bienvenidos. Así que dejaré la pregunta aquí, la haré comunidad y publicaré la respuesta yo mismo.