У меня может быть ответ для вас.
Переместите строку, в которой вы устанавливаете свои заголовки, на точку до того, как вы установите тип контента, и повторите ваш код следующим образом:
request.Headers.Add("SOAPAction", "http://tempuri.org/IWebService/GetMessage");
request.ContentType = "text/xml; charset=utf-8";
Я делаю это предложение на основе документации для свойства ContentType для объекта WebRequest от MS:
MS документы по WebRequest
Значение для этого свойства хранится в WebHeaderCollection. Если
WebHeaderCollection установлен, значение свойства потеряно.
Теперь я понимаю, что мы не явно устанавливаем WebHeaderCollection, но вы устанавливаете заголовок в этой коллекции, и это заставило меня подозревать, что Наименьшая вероятность того, что это может быть проблемой - сделать ваш существующий ContentType пустым и интерпретироваться как некоторое значение по умолчанию на входящей стороне веб-службы.
Может быть, длинный выстрел, но стоит попробовать.