Tenho notado isso com o PuTTY, mesmo no Windows 7 e 8 (nos PCs de mesa i7 principais). Eu uso monitores de alta resolução (2560 x 1440), e se a janela do PuTTY for grande e eu usar a roda do mouse para rolar, eu posso ver a repintura. É extremamente irritante.
Meu palpite é que é um problema com o mecanismo de composição do Windows em geral. Em um Mac, o terminal é incrivelmente suave e responsivo. O mesmo no Linux (Ubuntu 13.10) com o Compiz habilitado (e "janelas instáveis").
Eu olhei para algumas das alternativas de terminal SSH para Windows, como DameWare e TeraTerm, e é praticamente a mesma história sobre elas também. Minha "teoria" é Mac e Linux usam composição OpenGL (acelerada por GPU), enquanto o Windows é ... bem ... não sei o que está fazendo, mas não funciona tão bem.