Thank you. After some discussion on IRC, I solved the issue, but for completeness please allow me to quote the summary here:
I was playing around with Hercules, and for that I use x3270 which is an IBM mainframe terminal emulator. It installs a custom font, which is (drumroll) EBCDIC!
This is proven by starting "xterm -font 3270" which gives gives me an xterm with the same issue.
In StumpWM when starting, it tries to open a font called "9x15". If that font doesn't exist, it gets all fonts and uses the first one. In my case, that happens to be "3270" (presumably since it starts with a digit).