Right-to-left text in SSH is inconsistent

I am using SSH to connect to a server, where on occasion I need to work with some right-to-left language (e.g. Arabic). When I use *some* console software (e.g. lxterminal or xfce4-terminal), it works out just fine. In other terminals the text is backwards. Moreover, this behaviour is not even consistent across different computers (the xfce4-terminal behaves differently at home and in my office). What's worse is that the terminals are fine. Local files are displayed correctly. It is only when I connect via SSH that the problem occurs. So... what's the problem? Where is coming from? Is it the SSH, or the terminal, or somehow both?