Я нашел ответ по частям на Как добавить HTTP-заголовок в SOAP-клиент . Мне пришлось объединить пару ответов на этой странице, чтобы заставить его работать.
Dim svc As New WebServiceSoapClient()
Dim responseService As SoapResponseObject
Using (new OperationContextScope(svc.InnerChannel))
Dim auth = "Basic " + Convert.ToBase64String(Encoding.Default.GetBytes("userId:i2awTieS0mdO"))
Dim requestMessage = New HttpRequestMessageProperty()
requestMessage.Headers("Authorization") = auth
OperationContext.Current.OutgoingMessageProperties(HttpRequestMessageProperty.Name) = requestMessage
dim aMessageHeader = MessageHeader.CreateHeader("Authorization", "http://tempuri.org", auth)
OperationContext.Current.OutgoingMessageHeaders.Add(aMessageHeader)
responseService = svc.ListDistricts(requestService)
End Using
Одна ключевая вещь, о которой нужно знать, это то, что вызов мыльного клиента должен быть внутри оператора Using. В приведенном выше коде это следующая за последней строкой.