Benjamin,
Webservice nada mais é do que uma transferencia de xml. Existe a possibilidade do encode do websevice esteja errado. Verifice se os arquivos .disco e .wsdl estão com encode correto. Por padrão eles vêm com utf-8, mas levando em
conta que o sql tem a propriedade collation que define o padrão do sql, muitas vezes pode ocorrer conflitos.
A princípio você pode utilizar os métodos de encode e decod.
http://www.vbforums.com/showthread.php?t=287324
Um dia isso me aconteceu quando eu estava migrando o banco da empresa. O banco da minha empresa estava com a collation padrão e a outra base estava com SQL_Latin1_General_CP850_CI_AI. Quando eu migrei, os dados ficaram bem parecido com os que você
apresentou.
Samuel Fabel