Para responder minha própria pergunta:
Mudar de codificação restrita para codificação em hextile resolveu o problema com redesenho lento completamente.
Para adicionar alguns detalhes: notei que, durante o lento redesenho da tela, a cpu do cliente aumentava o uso de 100%. Eu estava usando codificação apertada e da página VNC Tight Encoder - resultados de comparação pode ser visto que a codificação apertada é bastante cpu intensivo quando comparado à codificação em hextile. Depois de alternar para o uso de cpu hextile max nunca é 100%, quase toda a largura de banda disponível é utilizada e redesenhar sempre leva menos de um segundo. Então, a CPU do cliente foi o gargalo.
Ou uma alternativa ainda melhor (menos largura de banda, baixo uso da CPU e parece ainda mais rápida que o hextile) é compilar x11vnc com suporte a TurboVNC e depois use cliente TurboVNC .