I suspect xdm does not support UTF-8 even though your environment may be set that way. It is is still down to the application to handle the interpretation of strings and the encoding they may contain.
To fix this issue, I removed the utf8 encoded strings and replaced them with with their ISO-8859-15 counterpart (you can get the list of iso-8859-15 sequences to use with man iso_8859-15). So this seemed to work for me:
xlogin*greeting: V\344lkommen till CLIENTHOST
xlogin*namePrompt: Anv\344ndare:
xlogin*fail: Fel l\366senord!
This also meant I didn't need to set anything in Xsetup either (I was originally trying to use sv_SE.utf8).
Well, first I guess I would point out that pretty much all terminals these days are "virtual" in the sense you talk about... even if the terminal is at the other end of a bona fide serial port. I mean, the days of VT-100s, Wyse terminals and other "physical", "real" terminals are pretty much gone!
That aside, let's say you want to detect what kind of Unicode support your terminal has. You can do this by writing test characters to is and seeing what happens. (You can make an effort to erase the test characters after you've written then, but the user may still see them briefly, or erasing them might not work properly in the first place.)
The idea is to ask the terminal to tell you its cursor position, output a test character, ask the terminal again to tell you its position, and compare the two positions to see how far the terminal's cursor moved.
To ask the terminal for its position, see here. Essentially:
echo -e "\033[6n"; read -d R foo; echo -en "\nCurrent position: "; echo $foo | cut -d \[ -f 2
Try outputting "é". This character takes 2 bytes in UTF-8 but displays in only one column on the screen. If you detect that outputting "é" causes the cursor to move by 2 positions, then the terminal has no UTF-8 support at all and has probably output some kind of garbage. If the cursor didn't move at all, then then terminal is probably ASCII only. If it moved by 1 position, then congratulations, it can probably display French words.
Try outputing "あ". This character takes 3 bytes in UTF-8 but displays in only two columns on the screen. If the cursor moves by 0 or 3, bad news, similar to above. If it moves by 1, then it looks like the terminal supports UTF-8 but doesn't know about wide characters (in fixed-width fonts). If it moves by 2 columns, all is good.
I'm sure there are other probe characters that you could emit which would lead to useful information. I am not aware of a tool that does this automatically.
Best Answer
Installing FbTerm was what I went with to get nice fonts in my CLI environment. It's a frame buffer terminal emulator (so no need for X org) that supports nice rendering of the same kinds of fonts you would use in a GUI.