I've been able to get around the same problem by appending the following to my vimrc
file:
" Terminal fixes
"
" These originate from some linux distribution's system vimrc. I can't say
" that I understand the details what's going on here, but without these
" settings, I've had problems like vim starting in REPLACE mode for
" TERM=xterm-256color (neovim is fine)
if &term =~? 'xterm'
let s:myterm = 'xterm'
else
let s:myterm = &term
endif
let s:myterm = substitute(s:myterm, 'cons[0-9][0-9].*$', 'linux', '')
let s:myterm = substitute(s:myterm, 'vt1[0-9][0-9].*$', 'vt100', '')
let s:myterm = substitute(s:myterm, 'vt2[0-9][0-9].*$', 'vt220', '')
let s:myterm = substitute(s:myterm, '\\([^-]*\\)[_-].*$', '\\1', '')
" Here we define the keys of the NumLock in keyboard transmit mode of xterm
" which misses or hasn't activated Alt/NumLock Modifiers. Often not defined
" within termcap/terminfo and we should map the character printed on the keys.
if s:myterm ==? 'xterm' || s:myterm ==? 'kvt' || s:myterm ==? 'gnome'
" keys in insert/command mode.
map! <ESC>Oo :
map! <ESC>Oj *
map! <ESC>Om -
map! <ESC>Ok +
map! <ESC>Ol ,
map! <ESC>OM
map! <ESC>Ow 7
map! <ESC>Ox 8
map! <ESC>Oy 9
map! <ESC>Ot 4
map! <ESC>Ou 5
map! <ESC>Ov 6
map! <ESC>Oq 1
map! <ESC>Or 2
map! <ESC>Os 3
map! <ESC>Op 0
map! <ESC>On .
" keys in normal mode
map <ESC>Oo :
map <ESC>Oj *
map <ESC>Om -
map <ESC>Ok +
map <ESC>Ol ,
map <ESC>OM
map <ESC>Ow 7
map <ESC>Ox 8
map <ESC>Oy 9
map <ESC>Ot 4
map <ESC>Ou 5
map <ESC>Ov 6
map <ESC>Oq 1
map <ESC>Or 2
map <ESC>Os 3
map <ESC>Op 0
map <ESC>On .
endif
There's more settings like that in https://gist.github.com/goerz/36015f27c2a5423c64a5f9dc03865f2c which might also help. The root cause is something not being right in the termcap/terminfo