When I had a Red Hat 5 box (not so long ago as you may think), I used to have a script which made a list of all files from installed packages which had not changed since installation, and then I split that up into root and /usr and used them as exclude lists for GNU tar to back up those partitions. The tar took maybe a couple of hours on a Pentium 150.
I resurrected that script last week and ran it on my Fedora Core 2 box (after fixing a few occurrences of bitrot). The tar process on /usr ran for something over 43 hours in total on a Pentium M 725 (1.6GHz). I guess I'll find a different way of doing that, then. :-)