You can do this with HashBackup too (I'm the author). There are sites using HB to backup terabytes of data. One of the larger sites has 25M files they backup every day.

1. Copy ssh public key to rsync.net server:

[jim@mb hbdev]$ scp ~/.ssh/id_rsa.pub XXXX@usw-s002.rsync.net:.ssh/authorized_keys
Password:
id_rsa.pub
100% 392 0.4KB/s 00:00

2. Create a local HashBackup backup directory:

[jim@mb hbdev]$ hb init -c hb
HashBackup build 1070 Copyright 2009-2013 HashBackup, LLC
Backup directory: /Users/jim/hbdev/hb
Permissions set for owner access only
Created key file /Users/jim/hbdev/hb/key.conf
Key file set to read-only
Setting include/exclude defaults: /Users/jim/hbdev/hb/inex.conf

VERY IMPORTANT: your backup is encrypted and can only be accessed with
the encryption key, stored in the file:
/Users/jim/hbdev/hb/key.conf
You MUST make copies of this file and store them in a secure location,
separate from your computer and backup data. If your hard drive fails,
you will need this key to restore your files. If you setup any
remote destinations in dest.conf, that file should be copied too.

Backup directory initialized

3. Create a dest.conf file in the backup directory:

[jim@mb hbdev]$ cat - >hb/dest.conf
destname rsyncnet
type rsync
dir NNNN@usw-s002.rsync.net:
password XYZZY

4. Enable dedup using up to 1GB of memory:

[jim@mb hbdev]$ hb config -c hb dedup-mem 1g
HashBackup build 1070 Copyright 2009-2013 HashBackup, LLC
Backup directory: /Users/jim/hbdev/hb
Current config version: 0
Showing current config

Set dedup-mem to 1g (was 0)

5. Create a test file, 10 x 10k random blocks

[jim@mb hbdev]$ dd if=/dev/urandom of=ran10k bs=10k count=1
1+0 records in
1+0 records out
10240 bytes transferred in 0.001602 secs (6392272 bytes/sec)

[jim@mb hbdev]$ cat ran10k ran10k ran10k ran10k ran10k ran10k ran10k ran10k ran10k ran10k >test100k

[jim@mb hbdev]$ ls -l test100k
-rw-r--r-- 1 jim staff 102400 Oct 15 14:20 test100k

6. Backup the test file:

[jim@mb hbdev]$ hb backup -c hb test100k
HashBackup build 1070 Copyright 2009-2013 HashBackup, LLC
Backup directory: /Users/jim/hbdev/hb
Using destinations in dest.conf
This is backup version: 0
Dedup enabled, 0% of current, 0% of max
/Users/jim/hbdev/test100k
Writing archive 0.0
Copied arc.0.0 to rsyncnet (11 KB 2s 5.0 KB/s)
Copied hb.db.0 to rsyncnet (4.3 KB 2s 2.1 KB/s)
Copied dest.db to rsyncnet (340 B 2s 162 B/s)

Time: 4.8s
Wait: 6.5s
Checked: 5 paths, 125418 bytes, 125 KB
Saved: 5 paths, 125418 bytes, 125 KB
Excluded: 0
Dupbytes: 0
Compression: 87%, 8.1:1
Space: 15 KB, 15 KB total
No errors

7. Create a different test file, with junk at the beginning, middle, and end:

[jim@mb hbdev]$ echo abc>junk

[jim@mb hbdev]$ cat junk test100k junk test100k junk >test200k
[jim@mb hbdev]$ ls -l test200k
-rw-r--r-- 1 jim staff 204812 Oct 15 14:24 test200k

8. Backup the new file:

[jim@mb hbdev]$ hb backup -c hb test200k
HashBackup build 1070 Copyright 2009-2013 HashBackup, LLC
Backup directory: /Users/jim/hbdev/hb
Using destinations in dest.conf
This is backup version: 1
Dedup enabled, 0% of current, 0% of max
/Users/jim/hbdev/test200k
Writing archive 1.0
Copied arc.1.0 to rsyncnet (42 KB 2s 15 KB/s)
Copied hb.db.1 to rsyncnet (4.6 KB 1s 2.3 KB/s)
Copied dest.db to rsyncnet (388 B 1s 207 B/s)

Time: 3.0s
Wait: 6.7s
Checked: 5 paths, 227898 bytes, 227 KB
Saved: 5 paths, 227898 bytes, 227 KB
Excluded: 0
Dupbytes: 122880, 122 KB, 53%
Compression: 79%, 4.8:1
Space: 47 KB, 62 KB total
No errors

9. What do the stats look like?

[jim@mb hbdev]$ hb stats -c hb
HashBackup build 1070 Copyright 2009-2013 HashBackup, LLC
Backup directory: /Users/jim/hbdev/hb

2 completed backups
353 KB file bytes checked since initial backup
353 KB file bytes saved since initial backup
0s total backup time
176 KB average file bytes checked per backup in last 2 backups
176 KB average file bytes saved per backup in last 2 backups
100% average changed data percentage per backup in last 2 backups
0s average backup time for last 2 backups
353 KB file bytes currently stored
2 archives
53 KB archive space
53 KB active archive bytes - 100%
5:1 industry standard dedup ratio
26 KB average archive space per backup for last 2 backups
6:1 reduction ratio of backed up files for last 2 backups
6.2 MB dedup table current size
4 dedup table entries
0% dedup table utilization at current size
2 files
6 paths
12 blocks
6 unique blocks
16,386 average variable-block length (bytes)

10. How much space are we using on the rsync server?

[jim@mb hbdev]$ ssh XXXX@usw-s002.rsync.net ls -l
total 309
-rw-r--r-- 1 XXXX XXXX 33 Oct 15 18:22 DESTID
-rw-r--r-- 1 XXXX XXXX 11216 Oct 15 18:22 arc.0.0
-rw-r--r-- 1 XXXX XXXX 42416 Oct 15 18:25 arc.1.0
-rw-r--r-- 1 XXXX XXXX 388 Oct 15 18:25 dest.db
-rw-r--r-- 1 XXXX XXXX 4308 Oct 15 18:22 hb.db.0
-rw-r--r-- 1 XXXX XXXX 4604 Oct 15 18:25 hb.db.1

11. By default, HB creates a local backup too. Delete the
local arc files (this is the file backup data)

[jim@mb hbdev]$ hb config -c hb cache-size-limit 0
HashBackup build 1070 Copyright 2009-2013 HashBackup, LLC
Backup directory: /Users/jim/hbdev/hb
Current config version: 2
Showing current config

Set cache-size-limit to 0 (was -1)

[jim@mb hbdev]$ hb backup -c hb /dev/null
HashBackup build 1070 Copyright 2009-2013 HashBackup, LLC
Backup directory: /Users/jim/hbdev/hb
Using destinations in dest.conf
This is backup version: 2
Dedup enabled, 0% of current, 0% of max
/dev/null
Removing archive 2.0
Copied hb.db.2 to rsyncnet (4.0 KB 1s 2.0 KB/s)
Copied dest.db to rsyncnet (404 B 7s 57 B/s)

Time: 2.5s
Wait: 9.2s
Checked: 3 paths, 5692 bytes, 5.6 KB
Saved: 3 paths, 5692 bytes, 5.6 KB
Excluded: 0
Dupbytes: 0
Compression: 29%, 1.4:1
Space: 4.0 KB, 66 KB total
No errors

[jim@mb hbdev]$ ls -l hb
total 30600
-rw-r--r-- 1 jim staff 65 Oct 15 14:03 HBID
-rw-r--r-- 1 jim staff 76 Oct 15 14:05 dest.conf
-rw-r--r-- 1 jim staff 4096 Oct 15 14:31 dest.db
-rw-r--r-- 1 jim staff 6291716 Oct 15 14:31 hash.db
-rwxr-xr-x 1 jim staff 9182624 Aug 10 09:45 hb
-rw-r--r-- 1 jim staff 139264 Oct 15 14:31 hb.db
-rw-r--r-- 1 jim staff 4308 Oct 15 14:22 hb.db.0
-rw-r--r-- 1 jim staff 4604 Oct 15 14:25 hb.db.1
-rw-r--r-- 1 jim staff 4012 Oct 15 14:31 hb.db.2
-rw-r--r-- 1 jim staff 6 Oct 15 14:31 hb.lock
-rw-r--r-- 1 jim staff 412 Oct 15 14:31 hb.sig
-rw-r--r-- 1 jim staff 511 Oct 15 14:03 inex.conf
-r-------- 1 jim staff 333 Oct 15 14:03 key.conf

12. Mount the backup as a FUSE filesystem:

[jim@mb hbdev]$ hb mount -c hb mnt >mount.log 2>&1 &
[1] 62772

13. What's in the mounted filesystem?

[jim@mb hbdev]$ ls -l mnt
total 8
drwx------ 1 jim staff 1 Oct 15 14:22 2013-10-15-1422-r0
drwx------ 1 jim staff 1 Oct 15 14:25 2013-10-15-1425-r1
drwx------ 1 jim staff 1 Oct 15 14:31 2013-10-15-1431-r2
drwx------ 1 jim staff 1 Oct 15 14:31 latest
[jim@mb hbdev]$ find mnt/latest
mnt/latest
mnt/latest/Users
mnt/latest/Users/jim
mnt/latest/Users/jim/hbdev
mnt/latest/Users/jim/hbdev/test100k
mnt/latest/Users/jim/hbdev/test200k
mnt/latest/dev
mnt/latest/dev/null

14. All file attributes are correct in the mounted filesystem:

[jim@mb hbdev]$ ls -l mnt/latest/Users/jim/hbdev
total 602
-rw-r--r-- 1 jim staff 102400 Oct 15 14:20 test100k
-rw-r--r-- 1 jim staff 204812 Oct 15 14:24 test200k

[jim@mb hbdev]$ ls -l test*k
-rw-r--r-- 1 jim staff 102400 Oct 15 14:20 test100k
-rw-r--r-- 1 jim staff 204812 Oct 15 14:24 test200k

15. Test the backup: are the remote and local files equal?

[jim@mb hbdev]$ time cmp test100k mnt/latest/Users/jim/hbdev/test100k
real0m2.464s
user0m0.001s
sys0m0.005s

[jim@mb hbdev]$ time cmp test200k mnt/latest/Users/jim/hbdev/test200k
real0m2.271s
user0m0.001s
sys0m0.004s

[jim@mb hbdev]$ time cmp ran10k mnt/latest/Users/jim/hbdev/test100k
cmp: EOF on ran10k
real0m0.005s
user0m0.001s
sys0m0.003s

(ran10k and remote test100k are equal for 1st 10k, which is correct)

Beta site is: http://www.hashbackup.com

There is a security doc on the site that has been reviewed by Bruce Schneier.