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 original- Public 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.