I've seen people complain about the speed issues of VNC on amiga due to the way in which the screen is captured.
Would it be possible to write a version using some sort of notification patch that literally intercepts all calls to graphics/intuition on the current (frontmost) screen in such a way as to add "damage rectangles" to a queue? This assumes, of course, that VNC itself is able to work with partial (rather than complete) screen refreshes.