Couple of dumb questions:
1) I looked at the sample WSDL and the XML declaration indicates UTF-8 encoding. Shouldn't this be KOI8-R? In that case, you could use any XML parser to interpret the content, make any changes, then serialize using the encoding of your choice.
2) Since this is coming over HTTP, do you have access to the charset parameter in the Content-Type field? If so, you can use that as a hint for the document encoding (although XML declaration should be used, IMHO).
`k.