I have a Ubuntu 13.10 server installed in VirtualBox on a Windows host. When I connect to it via SSH (tried Putty, Cygwin's OpenSSH and OS X terminal from a different machine) Emacs appears to be having screen (re)drawing issues. Here's my test scenario:
- emacs ~/.bashrc
- C-s HIST (incremental search for "HIST")
- keep hitting C-s (aka jump to the next search result)
After repeating no. 3 a few times, I end up with this:

The problem doesn't occur when using VirtualBox console. 12.04 works fine as well. Tried the emacs23-nox package, the latest emacs from ppa:cassou/emacs, emacs -q (skip start-up files), running it in a "screen" session, changing LC_ALL to C - all to no avail.
Any ideas what might be causing the issue?
TERM=xtermenvironment variable before starting emacs (export TERM=xtermorTERM=xterm emacs) or look in your Putty settings for the terminal type.