>Got to http://msdn.microsoft.com/library/default.asp?url=/library/en-us/cpguide/html/cpconusingsoapheaders.asp

The link provided follows the same format to manipulate a SOAP header as I am doing. That also requires the client to follow strict specifications.

From what I know, there isn't any other approach to manipulate the SOAP header from the client side. Without applying a strict guidelines, it can't be done. I know MS is working on extanding that flexiblity for other versions. But, for now, we have to deal with it as is or to use other approaches, such as passing additional parameters at each method call for every request.