Odd problems with vim over ssh to remote linux machine
I would recommend changing from x-term256color to xterm for your TERM variable as that seems to have resolved my similar issues.

The things I saw (in addition to the question's symptoms) are often to have  line over-flow issues within the vi session. That is if I type beyond a certain number of columns then the rest of the text is put onto the next line (i.e. with a new line \n character in place). This overflowed text is not displayed in the current vi session but I will see it after reopening.

Another problem is occasionally the cursor is displayed on one line but I will start editing the next line down..... a real pain when you are writing code!