motion detection is not as easy as it should be

Yeah, and we're working on more or less the exact rolling hash idea you described. It was kinda weird to see you describe the same approach here... It's still work in progress, but there's a few PNGs here that shows the current status: http://people.freedesktop.org/~krh/rolling-hash/

With just a few MULs per pixel, we can detect if a 32x32 blocks starting at that pixel appears in the previous frame. This should basically be as good as any scrolling/copyarea hint we could've gotten from X or a toolkit, and it detects duplicate blocks in may cases where applications don't scroll but just re-render (like resizing). And of course this technique applies to both fullscreen remote display or per-window remote display.