Can you check if the package is installed properly? rpm -qlp package_name.rpm will give you the list of files to be installed by the rpm file. Then, you have to verify if those files are really installed properly on the system.
Seems like somehow the RPM database is not getting updated. If it's the issue with a particular RPM file, I would say that there is certainly an issue the way the RPM was packaged.