Not an answer but a workaround
By trying different TERM values I found one that makes Vim work: screen
So a workaround could be to add the following code to the shell profile file:
[ "$TERM" = xterm-256color ] && TERM=screen
While I can make do with it, I would prefer to understand where the problem lies exactly.