Create a cell, say, backup.awesmoe.org. Use a separate database to translate bizare volume names into a particular backup set (say, ab.d92fgaf9a8as0 to backup of foo.bar.awesmoe.org on 23 July 2005 03:28 UTC). You can mount these volumes in a tree, say /afs/backup.awesmoe.org/bydate/2006/07/23/foo.bar.awesmoe.org-200607230328 or /afs/backup.awesmoe.org/byhost/foo.bar.awesmoe.org/2006/07/23/.... Set acls to use list so that machine admins can see files (prolly have to use hashed list names as well --- what is limit on pts list name length?) Can even acl off so that various people can see certain bits from machines.
Use rsync as backup mech, can do incrementals. Merge incrementals to create fulls.
To backup afs, vos dump volumes, suck back into the backup cell.