Not sure what's going on here, but if I open a file in emacs (no window mode), and just do a search (ctrl-s), the buffer gets garbled. It fixes itself when I ctrl-l, but that's annoying to have to do so frequently.
I'm using OS X's Terminal declaring terminal as xterm-256color. Text encoding Unicode (UTF-8).
I'm ssh-ing to a VM and launching emacs in that VM.
Here's an example: