Somehow it is NOT in the rpm database ... that is why yum thinks it is not there.
This could also happen accidentally with multilib installs (it looks like you do have this possible issue).
When a system is installed in c5, the default behavior is that both i386 and x86_64 packages are installed. It looks like you have removed the i386 packages as a rpm -q tar shows only one package (I do this too ... I think it is a good idea). There is a potential problem though ... both versions of tar (the i386 and x86_64 versions) provide /bin/tar ... when removing the i386 version, sometimes the database will remove /bin/tar from the list of installed packages even though the x86_64 version is still installed.
This can lead to the same kind of issue that you had ... and it is possible to get it silently. So, I will add a .rpmmacros entry to root so that rpm -qa also shows "E-V-R.<arch>", remove all i[3,4,5,6]86 packages, then I make an entry to exclude multilib like this in yum.conf:
multilib_policy=best
Then I reinstall all x86_64 packages that had i386 packages removed (I create a list before I remove them).
So, if you are doing "rpm -e tar.i386" (I suspect you are since there is only one currently installed) ... that might also be the source of the problem.
This is no longer a problem in CentOS-6 as anaconda does not install i386 packages on x86_64 installs by default ... but they are installed by default on CentOS-5.
from memory i have not deliberately removed the i386 package, but you are right it is not there, however rpm does seem to know about /bin/tar
# rpm -ql tar /bin/gtar /bin/tar <snip>
although i agree its something rpm db related as reinstalling tar via rpm rather than yum solves the problem, however i dont see how this situation has arisen.