<<snip>>
All this leads me to the conclusion that there are only some selected packages corrupt (and I don't want to reinstall the machine). Would Installing/Repairing from DVD help?
If you have packages newer than what is on the dvd, I don't think they will get replaced. You might get away with removing the packages from the rpm database only and then re-install them, but yum probably wouldn't help you here.