I've noticed this with PuTTY even on Windows 7 and 8 (on core i7 desktop PCs). I use very high resolution monitors (2560 x 1440), and if the PuTTY window is large and I using the mouse wheel to scroll, I can see the repaint. It's extremely annoying.
My guess is it's a problem with Window's compositing engine in general. On a Mac, the terminal is awesomely smooth and responsive. Same on Linux (Ubuntu 13.10) with Compiz enabled (and "wobbly windows").
I've looked at some of the SSH terminal alternatives for Windows, like DameWare and TeraTerm, and it's pretty much the same story on these too. My "theory" is Mac and Linux use OpenGL compositing (GPU accelerated), whereas Windows is.... well.... not sure what it's doing, but it doesn't perform as well.