I discovered on a machine a while back that if you set a Windows machine to use the VGA driver (not simply set the resolution to be 640x480), the machine's performance (at least as far as VNC was concerned) was awful. Make sure that you use the correct driver for your video card, but set the resolution to be as low as you can stand.