x11vnc is slow, but using only 10% of available bandwidth

To answer my own question:

Switching from tight encoding to hextile encoding resolved the problem with slow redrawing completely.

To add some detail: I have noticed that during slow redrawing of the screen the cpu on the client was spiking to the 100% usage. I was using tight encoding and from the page VNC Tight Encoder - Comparison Results it can be seen that tight encoding is quite cpu intensive when compared to hextile encoding. After switching to hextile max cpu usage is never 100%, almost the whole available bandwidth is utilized and redrawing always takes less than a second. So the client's CPU was the bottleneck.

Or even better alternative (less bandwidth, low cpu usage and seems even faster than hextile) is to compile x11vnc with TurboVNC support and then use TurboVNC client.

The reason is that the screen capture/renderer is inefficient. Many different VNC implementations play around with this to achieve better performance.

If you don't need to reflect exactly what is on the local console, a better solution is NoMachine's NX or FreeNX as a remote desktop environment. Performance is day and night compared to VNC even over WAN links.