Hi Daniel,
Did you happen to investigate why rsync -S is taking so much time? If it

doesn't deal with sparse file the way one expects, this option is probably

broken. Also have you already tried something like the advice in

http://lists.samba.org/archive/rsync/2003-August/007000.html ?
Anyway, I think the way to go is using tar. It preserves the sparseness

property of the files, so something like this could work: If you tar the

file without using compression, you would get a file the size of the

sparsefile, with a lot of zeroes in it. Then use a run-length encoding on it

to collapse the zeroes.
Sync this file with rsync.
On the destination machine do it in reverse. Using pipes you don't even need

the physical space of the whole sparse file, just the space requirement of

the actual data in the sparse file; or transfer it immediately you don't

need any space at all.
Example (with a pseudo rle program):
tar cf - sparsefile | rle -input - -output sparsefile.tar.rle
The code for run-length encoding is there in zlib, but unfortunately

compress/gzip doesn't have an option to use it. You'd either need to hack

this in yourself, or use one of the many implementations found when

searching for rle. This would give you the option to modify it, to just

rl-encode the zeroes.
David