Here is the final version to resolve that issue. I brought the subclass of the proxy inside the .vb file having the class which executes it all. This class creates an instance of an object of the subclass instead of the main reference. The main class exposes publically cCertificate, which I need to define, and cXmlReponse, which is the XML response I receive back from the entire envelope:

' Use to override some methods in the proxy
Public Class MyWebServiceClient

    Inherits MyWebService.MyWebService

    Private oMyClass As MyClass = Nothing

    Public Sub New(ByVal toMyClass As MyClass)
        oMyClass = toMyClass
    End Sub

    ' Override the GetWebRequest() method in the proxy
    Protected Overrides Function GetWebRequest(loUri As Uri) As System.Net.WebRequest
        Dim loHttpWebRequest As System.Net.HttpWebRequest = Nothing

        ' Initialization
        loHttpWebRequest = DirectCast(MyBase.GetWebRequest(loUri), System.Net.HttpWebRequest)

        ' Add the header
        loHttpWebRequest.Headers("certificate") = oMyClass.cCertificate

        Return loHttpWebRequest
    End Function

    ' Override the GetWebResponse() method in the proxy
    Protected Overrides Function GetWebResponse(loWebRequest As System.Net.WebRequest) As System.Net.WebResponse
        Dim loHttpWebResponse As System.Net.HttpWebResponse = Nothing
        Dim loXmlDocument As System.Xml.XmlDocument = New System.Xml.XmlDocument

        ' Initialization
        loHttpWebResponse = DirectCast(MyBase.GetWebResponse(loWebRequest), System.Net.HttpWebResponse)

        ' Load the response stream into an XmlDocument
        loXmlDocument.Load(loHttpWebResponse.GetResponseStream())

        ' Make it available
        oMyClass.cXmlResponse = loXmlDocument.OuterXml

        Return loHttpWebResponse
    End Function

End Class

I adjusted the class name in this example, so as the Web Service reference, so to protect some privacy. But, that should give you an idea of the approach I have taken.

Thanks for all the help, this has brought some additional related topics that were useful in the discussion.