Couple of dumb questions:
I looked at the example WSDL and the encoding declaration in the XML is UTF-8, not KOI8-R. I'm not an expert on KOI8-R, but a little googling leads me to believe that it's not UTF-8 compatible (natch, based on your findings). Is there a reason why KOI8-R is not declared as the encoding for the document? You can use any XML parser to suck up the content in that case.
When retieving the WSDL via HTTP, is the Content-Type field providing a charset parameter? If so, you can use that to decode apporpriately.
cheers,
`k.