The RPM indexes on one of my CentOS 4.4 machines got corrupted last weekend, which caused some issues on one of the servers I was trying to update. To fix this issue, I removed the files with two underscores in /var/lib/rpm:
$ rm -f /var/lib/rpm/__
And then I recreated the indexes by running rpm with the "--rebuild" option:
$ rpm --rebuild
This experience taught me a few things:
1. The package header information is stored in /var/lib/rpm/Packages
2. RPM has an "--initdb" option to initialize the RPM database
3. I really don't care for RPM