Já experimentou a opção --verify para tentar executar uma verificação em seu backup e ver o que o rdiff declara? Também olhando para outras saídas de --verify, parece que o rdiff usa assinaturas SHA1 e não MD5 como mecanismo de verificação. Eu também estava lendo que, aparentemente, se você tem arquivos com vários links para eles, que, ao restaurar o rdiff, pode não colocá-los exatamente como estavam. Há alguém que aparentemente criou um patch, mas não sabe se foi abençoado, incluído ou até mesmo amplamente disponível.
Eu estava lendo este tópico depois de fazer algumas pesquisas no rdiff:
você pode usar os links na página para voltar e avançar para ver o tópico inteiro, mas essa página me deu muitas das minhas sugestões para o que eu digitei aqui.
Espero que ajude.