You haven't mentioned where or how your string is stored (that is populated with your WCF.InboundHeaders), however I would use a simple fragment of XPath to extract the UserId. If you were extracting this using a C# helper, you could do something along the lines of (note, this is untested, however its pretty much there):
XmlDocument doc = new XmlDocument();
doc.Load([WCF.InboundHeaders Xml Fragment]);
// Create an XmlNamespaceManager to add 'soap-envelope' namespace
XmlNamespaceManager nsmgr = new XmlNamespaceManager(doc.NameTable);
nsmgr.AddNamespace("s", "http://www.w3.org/2003/05/soap-envelope");
// Select the UserId
XmlNode userId = doc.SelectSingleNode("/headers/s:userid", nsmgr);
Console.WriteLine(userId.InnerXml);
You may also want to serialize the Xml fragment into a .Net object and retrieve the UserId in that manner.