Hola chicos.
Finalmente lo resolví. Efectivamente no se trataba de algo extenso si no más bien de saber qué hacer.
Una vez aclarado el tema con la gente del servicio, resulta que las credenciales debían viajar en la petición HTTP, y no en la petición SOAP que va dentro de la petición HTTP.
Por lo tanto la AUTH_HEADER (o cabecera de autenticación) debía ser una cabecera HTTP, y no una cabecera SOAP.
Y sin más, a continuación les dejo cómo construir una cabecera de autenticación HTTP, con autenticación básica:
Primero aclarar que con agregar "Referencia Web" sería suficiente. Imagino que habrá la forma de hacerlo por "Referencia de Servicio", pero no me he querido pelear más con esto.
Entonces, primero construímos una clase que herede de la clase proxy del servicio.
Código VB.NET:
Ver originalPublic Class ServicioPruebaHeredado : Inherits ServicioPrueba.DBSOAPMethods
Protected Overrides Function GetWebRequest(ByVal uri As Uri) As System.Net.WebRequest
Dim webRequest As System.Net.HttpWebRequest = DirectCast(MyBase.GetWebRequest(uri), System.Net.HttpWebRequest)
Credentials = New Net.NetworkCredential("UserName", "Password")
PreAuthenticate = True
Dim misCredenciales As System.Net.NetworkCredential = TryCast(Credentials, System.Net.NetworkCredential)
If Not misCredenciales Is Nothing Then
Dim authInfo As String = ((If((misCredenciales.Domain IsNot Nothing) AndAlso (misCredenciales.Domain.Length > 0), misCredenciales.Domain + "\", String.Empty)) + misCredenciales.UserName & ":") + misCredenciales.Password
authInfo = Convert.ToBase64String(System.Text.Encoding.Default.GetBytes(authInfo))
webRequest.Headers("Authorization") = "Basic " & authInfo
End If
Return webRequest
End Function
End Class
OK, esta era la parte difícil
Ahora simplemente se trata de invocar a esta clase, en vez de a la clase proxy original, y trabajar como siempre, llamando a sus funciones y métodos.
Lo que conseguimos a través de la clase heredada, es que se le añada, a cada petición, una cabecera de autenticación con las credenciales.
Espero que le sirva a alguien.
Saludos.