I set up automated verification on the 4 backups servers on every backup job that they run. That simply involved the correct usage of the --verify option to rdiff-backup. This option calculates SHA1 checksums on files in the backups and compares them to the backups metadata. I don't put much stock in this process but feel that it is necessary to actually perform. Besides, the overhead is pretty low since the processing stays entirely on the backups server.
Rdiff-backup also sports a --compare-hash option in addition to --verify. The --compare-hash option actually calculates SHA1 checksums on the source server to compare to what is in the backups metadata. That seems nice but is probably going to be CPU intensive on the source server which I don't want. Still, I might just set it up as a weekly process to run in off hours. We'll see.
One thing that I learned is that Python < 2.4 doesn't support the decorator syntax in 2.4 and up. Rather than monkey with the small syntax differences and determining at runtime which Python version was executing the script, I just decided not to use decorators in one place where it would have been nice (but not necessary) to do so.
The next piece of this project will be to automate the test restores. That'll be slightly more tricky but ought to be satisfying to actually program up.