Зачем прокси кодировать что-либо?
Описывается ли этот сервис WSDL? Если да, то смогли ли вы создать прокси-класс с помощью «Добавить ссылку на службу» или svcutil.exe? Разве у прокси-класса нет правильной подписи для операции, которую нужно вызвать?
Если прокси-класс не имеет правильной подписи, вы не сможете его использовать. Вы должны будете использовать класс WebClient самостоятельно. Создайте XML в соответствии со схемой, затем отправьте его через WebClient.