Você não menciona a marca do seu dispositivo NAS. Alguns dispositivos NAS high-end (NetApp, Isalon, DataDomain) suportam a desduplicação.
Isso permitiria fazer backup diário completo e todos os dados seriam "desduplicados" no dispositivo. Essa deduplicação / compactação é completamente transparente para o usuário (/home/user/myimages/fooimage.tiff é exatamente igual em todo o histórico de backup).
Eu fiz isso para um sistema de arquivos de 300GB, e conseguimos manter quase dois anos de backups em um único appliance.
E eu sei que isso é um pouco tangente, mas algumas soluções mais baratas agora devem estar disponíveis usando o ZFS da Sun. O ZFS também desduplica, embora seja um pouco imaturo em comparação com as ofertas do Netapp ou do DataDomain. Da próxima vez que eu olhar, estou pensando no ZFS, possivelmente quando FreeNAS 8.0 sai.
No entanto, se você não tiver um desses, o 'rdiff-backup' funciona muito bem também.