tried deleting /var/lib/rpm/__* after killing all yum processes?
Yum has command line options to do its housecleaning which I would try first.
yum help clean
What does deleting the __db files do that the yum clean all doesn't? (which I notice doesn't delete those specific files)