Ok, after desparate searching and figuring I guess I found it. Debian keeps a link from /usr/bin/xemacs to /etc/alternatives/xemacs and this pointed to /usr/bin/xemacs21 which obviously has not idea about any coding system. After installing xemacs21-nomul and chnaging the link to point to this executable I got my prompt again.
So if anyone gets into trouble as I did, you may know why ;-(
Regards Friedrich