Какая технология используется для разработки веб-службы?
В .NET при передаче параметра XML в виде строки .NET Framework кодирует его на клиенте и декодирует обратно на сервер, что абсолютно правильно.
Если веб-сервис разработан по какой-то другой технологии, я думаю, им нужно выполнить декодирование строки, чтобы преобразовать ее обратно в строку XML.