Этот ответ в значительной степени основан на ответе Дарина Димитрова - если вы считаете его полезным, пожалуйста, подпишите его ответ.
В моем случае веб-служба хотела, чтобы значение JSESSIONID использовалось как cookie, а не как разное значение заголовка.
Кроме того, мой клиент WCF использовал прокси-код, сгенерированный средством Visual Studio Project - Set Service Reference, которое, как я считаю, аналогично использованию программы wsdl.exe.
// Session ID received from web service as response to authentication login
private string _sessionId;
// This code needed to add the session ID to the HTTP header as a JSESSIONID cookie value
using (MyServiceClient myServiceClient = new MyServiceClient())
using (new OperationContextScope(myServiceClient.InnerChannel))
{
HttpRequestMessageProperty httpRequestProperty = new HttpRequestMessageProperty();
httpRequestProperty.Headers.Add("Cookie", "JSESSIONID=" + _sessionId);
OperationContext.Current.OutgoingMessageProperties.Add(
HttpRequestMessageProperty.Name, httpRequestProperty);
myServiceClient.someMethod();
}