This appears to be a relatively recent regression in the emacs-25 
branch. It may not be easy to bisect. I first noticed it a few days ago, 
and the display glitches are pretty bad.

I just now reproduced the problem by using ssh to log into a Fedora 23 
x86-64 system running emacs-25 (commit 
dc5e65b5deb2f5b67f6c3a06ae81c6b074bd4b56) from my laptop, which is 
running Ubuntu 12.04.5 gnome-terminal in a 37x80 window (TERM=xterm in 
the environment). I have seen the problem from recent Ubuntu clients as 
well.

I changed to the Emacs source directory and ran the command

src/emacs -nw -Q src/conf_post.h

I then typed:

C-s h a s _

The screen display was messed up at this point; see attached image. 
Notice that the minibuffer says "hhs_" (with a highlighted second "h") 
instead of the correct ("has_").

The problem is not easily reproducible. Often Emacs works. Sometimes it 
does not, and the screen keeps getting more and more corrupted as time 
goes on. Symptoms often differ.

I just now tried a similar recipe (without the '_'), and this time Emacs 
contained the following text at the start of the (now-modified) 
conf_post.h buffer:

1;3201;0chas/* conf_post.h --- configure.ac includes this via AH_BOTTOM

and view-lossage showed the following:
  C-s C-s C-s [isearch-forward]
  ESC [ > [nil]
  1 [self-insert-command]
  ; [c-electric-semi&comma]
  3 [self-insert-command]
  2 [self-insert-command]
  0 [self-insert-command]
  1 [self-insert-command]
  ; [c-electric-semi&comma]
  0 [self-insert-command]
  c [self-insert-command]
  h [self-insert-command]
  a [self-insert-command]
  s [self-insert-command]
  ESC x [execute-extended-command]
  v [self-insert-command]
  i [self-insert-command]
  e [self-insert-command]
  w [self-insert-command]
  - [self-insert-command]
  l [self-insert-command]
...


My guess is that there is something wrong with the initial handshake 
with the terminal, to find out its characteristics; if memory serves 
this is something we've fiddled with in emacs-25 reasonably recently.