How to authenticate call to a SOAP service with basic authentication

I have some legacy code that calls a SOAP service endpoint from a NET application. The service stub is created by VS from the WSDL file And I have the code as below:

Dim ws As servicens.AddPermitClient = New servicens.AddPermitClient()
ws.ClientCredentials.UserName.UserName = "user"
ws.ClientCredentials.UserName.Password = "pw"

Dim wsRequest As servicens.AddPermitRequestType = New servicens.AddPermitRequestType()
' setup various params
wsRequest.Account = "..." ' ... etc

Dim wsResponse = ws.addPermit(wsRequest)
returnMessage = wsResponse.ReturnMessage
returnCode = wsResponse.ReturnCode

The service configuration in web.config is

<endpoint address="https://servicens.com:443/Permit/services/AddPermit"
    binding="basicHttpBinding" bindingConfiguration="AddPermitServiceSoapBinding"
    contract="servicens.AddPermit" name="AddPermit" />
</client>

and the binding configuration

<basicHttpBinding>      
  <binding name="AddPermitServiceSoapBinding">
    <security mode="Transport" >
      <transport clientCredentialType="Basic"/>
    </security>
  </binding>
</basicHttpBinding>

This code worked just fine for years till about a week ago when I stated to get error "Unable to fetch Office" and ReturnCode 400.

I contacted the developer of the service for the error and they told that the request is unauthenticated and this is the error report in this case.

They told that our request misses the authentication header in the request I inspected the request with Fiddler and indeed in the headers section there is no Authorization header

and in the Auth tab the message:

No Proxy-Authorization Header is present.
No Authorization Header is present.

As you can see in the code above I attempt to add the client credentials to the request, but somehow they don't end-up in the header section of the message.

How can I add Authorization header?

And, additionally, how this worked in the first place till now? Maybe they updated the service recently and just added the authentication requirement?

I finally figured out how to handle the problem I assume the provider changed the service meantime to require Authorization header, and I found the following way to add it

Using scope = New OperationContextScope(ws.InnerChannel)
  Dim encoded = System.Convert.ToBase64String(System.Text.Encoding.GetEncoding("ISO-8859-1").GetBytes(username + ":" + password))
  Dim basicAuth = "Basic " + encoded
                        
  WebOperationContext.Current.OutgoingRequest.Headers.Add("Authorization", basicAuth)

  Dim wsResponse = ws.addPermit(wsRequest)
  '....
end using

This added the Authorization header in the request and the call executed successfully.

I still didn't figured out how it worked before. The only reasonable assumption is that they just introduced the need for the Authorization header in a recent version