My language contains non ASCII character. How do I stop Remote Keyboard from turning them into garbage?

The problem lies with your telnet client. See if you can configure it to use UTF-8 as it's character encoding. With PuTTY, this is set under Window → Translation.