UTF-8 читабельно. ASP.NET должен уметь читать это нормально. Если он передается с Content-Type, для параметра charset которого установлено значение, отличное от UTF-8, вам может потребоваться указать ASP.NET принудительное декодирование в UTF-8. Используйте Fiddler и выясните, как выглядит HTTP-запрос, и обратите особое внимание на параметр Content-Type.
Если у вас кодировка вывода, отличная от UTF-8, вы все равно сможете правильно выводить символы, если декодируете их с правильной кодировкой. Какая у вас выходная кодировка? Какая кодировка используется веб-службой? Изобразите ответ на эти вопросы (используя Fiddler), и ваше решение должно быть очевидным.