ssh pseudoterminal special character problems

So I have the following situation: I have a host that exhibits unexpected behavior when using ssh -t combined with tmux. If I call ssh -t my-problem-host tmux non-ascii characters (e.g. €) are displayed as _. If I connect without calling tmux, there is no problem. For example ssh -t my-problem-host bash followed by manually entering tmux is OK, while ssh -t my-problem-host bash tmux is not OK. Other strange behavior outside of tmux: If I use ssh -t my-problem-host vim and enter a special character, I get the special character and a space. If I use ssh -t my-problem-host mc and type a special character, I get two questions ??. I also have this problem only with a single host and would like to know what causes this and how this can be fixed. Essentially ssh -t seems to cause problems, the host seems to have a strange pseudo-terminal.