Lo que yo realice , es abrir el simbolo del sistema de Visual Studio 2010, en modo administrador, y ejecute tal y como indica la pagina , svcutil.exe http://nazca.gotdns.com:1234/personaService.svc?wsdl, ya que el svcutil.exe esta incluido dentro del visual studio y m genero tanto la clase como. el archivo de config, aora los adheri a un proyecto pero a pesar de ello no logre  conectarme te facilito el proyecto y los archivos generados, para haber si logras acer la conexion. Cualquier cosa me comentas.

El link
http://www.mediafire.com/?z1r0ag0qfk88v0b

Alli estan los archivos haber si logras conectarlo ocando en algo

Yo tembien quiero utilizar ese web service, estoy con el mismo dilema, la manera que yo lo probe, desde .net con visual studio 2010, ir a mi proyecto , click derecho, agregar referencia del servicio, y puse la url del servicio , y automaticamente lo instancio a mi proyecto y lo pude usar, posterior a ello al ejecutarlo me aparece el error que mencione anteriormente, hasta alli llege ahora no se que mas hacer.
Haber si nos comentas como te resulto.

Descargue tu ejemplo, y al momento de correrla indica que no es posible la conexión con el servidor remoto, también indicas que se tiene que actualizar la libreria cuando cambia la estructura de la reniec, como puedo hacer eso?? , o como conozco la estructura de la reniec, para que puedas rescatar esos datos.??? ayuda porfavor.

Hey Amigo estoy en el mismo dilema cuando quiero consumir datos me sale el siguiente error, y suspongo que tambien debe ser por el captcha
Tu lo llegaste a Resolver.
Este es el error :
El mensaje con la acción 'http://nazca.gotdns.com:1234/PersonaService/IPersonaService/GetByDNI' no se puede procesar en el destinatario debido a una falta de coincidencia de ContractFilter en EndpointDispatcher. La razón puede ser que los contratos no coinciden (falta de coincidencia de las acciones entre el remitente y el destinatario) o que el enlace/seguridad no coinciden en el remitente y el destinatario. Compruebe que el remitente y el destinatario tienen el mismo contrato y el mismo enlace (incluidos los requisitos de seguridad, por ejemplo Message, Transport, None).