You have to have the correct terminal type in your TERM variable, and inform the remote host of your terminal size with stty rows <rows> columns <cols>.
Nowadays, I only have to do this when dealing with embedded hosts over serial consoles; the SSH protocol knows how to communicate these settings from the local system to a remote Unix-like kernel (or to generate the settings in the case of a client like PuTTY).
Maybe you have some shell .profile script on the remote host which is putting an inappropriate value into TERM or messing up the TTY info with bogus stty commands.
[UPDATE]
The example display now shown in the question looks very much like horizontal scrolling. Just type 0 to jump to the leftmost column.
You can disable horizontal scrolling using :set wrap; then long lines are wrapped. To enable horizontal scrolling again, use :set nowrap.