If I run
$ /usr/lib/kde4/libexec/kmailservice 'mailto:?subject=тема'
kmailservice shows subject correctly. But
$ xdg-email 'mailto:?subject=тема'
runs kmail with 'Ñема' subject. After such change

--- xdg-email   2011-01-01 13:03:14.000000000 +0300
+++ xdg-email.fix       2011-01-13 21:06:07.376069765 +0300
@@ -462,7 +462,7 @@ open_kde()
         KMAILSERVICE=`which kmailservice 2>/dev/null`
     fi
     # KDE uses locale's encoding when decoding the URI, so set it to UTF-8
-    LC_ALL=C.UTF-8 $KMAILSERVICE "$1"
+    $KMAILSERVICE "$1"
     kfmclient_fix_exit_code $?
 
     if [ $? -eq 0 ]; then

kmail shows subject correctly.

$ locale
LANG=ru_RU.UTF-8
LC_CTYPE="ru_RU.UTF-8"
LC_NUMERIC="ru_RU.UTF-8"
LC_TIME="ru_RU.UTF-8"
LC_COLLATE="ru_RU.UTF-8"
LC_MONETARY="ru_RU.UTF-8"
LC_MESSAGES="ru_RU.UTF-8"
LC_PAPER="ru_RU.UTF-8"
LC_NAME="ru_RU.UTF-8"
LC_ADDRESS="ru_RU.UTF-8"
LC_TELEPHONE="ru_RU.UTF-8"
LC_MEASUREMENT="ru_RU.UTF-8"
LC_IDENTIFICATION="ru_RU.UTF-8"
LC_ALL=