It appears write is interpreting the high bit as ‘meta-’ (Meta+key or Esc key). A quick look at the source code (function wr_fputs() in write.c) confirms this: control characters are shown as ^X, characters with the high bit set are shown as M-X. Locale settings, terminals and encodings have nothing to do with it, I'm afraid. write is just 7-bit.
Now, I'm a Unicode freak, but this makes a perverted sort of sense. write just opens the target TTY and writes to it (there's no magic involved). There's no easy way to get the character encoding understood by the process controlling the remote TTY. And even if there were, not all encodings are convertible to all other encodings. And without conversion, transmitting a message in KOI8-R to an ISO-8859-1 console would fail miserably. Since write takes the simplistic, 70s approach, this is what we get.