I believe the label should still be 'selinux_config_t' (even though SElinux is currently disabled) like in the following example:

[root@rhel6 ~] # grep ^SELINUX= /etc/selinux/config
SELINUX=disabled
[root@rhel6 ~] # ls -lZ /etc/selinux/config 
-rw-r--r--. root root system_u:object_r:selinux_config_t:s0 /etc/selinux/config

It almost seems as though at one point SELinux was not enabled then re-enabled (possibly)? Which shoudl have relabeled the entire file systems after the reboot.

I'm sure support could get this sorted in no time ;-) But, if I was in this situation, I would want to test a few things. I would first try to relabel the entire system, which can take quite a while.
DISCLAIMER: I have heard of systems being so out of compliance that the person first needed to set SElinux to PERMISSIVE, then relabel, the set to ENFORCING. (i.e. could not simply go to ENFORCING).

Check out the following doc (and the Note at the bootom)
https://access.redhat.com/documentation/en-US/Red_Hat_Enterprise_Linux/6/html/Security-Enhanced_Linux/sect-Security-Enhanced_Linux-Working_with_SELinux-Enabling_and_Disabling_SELinux.html

And.. this is part of the reason I love helping out at the Portal - I just discovered a justification why you should use PERMISSIVE rather than DISABLED (from the Sec Doc above)
"Also, files created while SELinux is disabled are not labeled."

My pleasure - I wish I knew the "silver bullet" but.. I think you'll get this resolved.

This thread made me also wonder about something else (when you mentioned grub.conf) - I guess I had not considered that to be the culprit. For the benefit of others that happen upon this thread, grub.conf could actually have been playing a role in this as well (though Dan said he checked there)

https://access.redhat.com/solutions/3176

Make sure SELinux is not disabled using Grub boot loader. 
Search /boot/grub/grub.conf for selinux
# egrep -i 'selinux|enforcing' /boot/grub/grub.conf
(/boot/efi/EFI/fedora/grub.cfg) for Fedora, with EFI.

Good find!
BTW - If you use Satellite (or RHN probably allows this also) you can create a profile of a "known good" system and then compare your other systems to see what the package differential is. Otherwise, you might want to run a rpm -ql | sort on both systems and run an sdiff against the 2 outputs.

After looking at the file list of selinux-policy-targeted - I guess that makes sense. I thought the contexts were acquired by looking at the rpm manifest. I need to do some learning ;-)

[root@apoc files]# grep \/etc\/selinux /etc/selinux/targeted/contexts/files/file_contexts
/etc/selinux(/.*)?  system_u:object_r:selinux_config_t:s0
/etc/selinux/([^/]*/)?seusers   --  system_u:object_r:selinux_config_t:s0
/etc/selinux/([^/]*/)?users(/.*)?   --  system_u:object_r:selinux_config_t:s0
/etc/selinux/([^/]*/)?logins(/.*)?  system_u:object_r:selinux_login_config_t:s0
/etc/selinux/([^/]*/)?policy(/.*)?  system_u:object_r:semanage_store_t:s0
/etc/selinux/([^/]*/)?setrans\.conf --  system_u:object_r:selinux_config_t:s0
/etc/selinux/([^/]*/)?contexts(/.*)?    system_u:object_r:default_context_t:s0
/etc/selinux/([^/]*/)?contexts/files(/.*)?  system_u:object_r:file_context_t:s0
/etc/selinux/([^/]*/)?modules/semanage\.read\.LOCK  --  system_u:object_r:semanage_read_lock_t:s0
/etc/selinux/([^/]*/)?modules/semanage\.trans\.LOCK --  system_u:object_r:semanage_trans_lock_t:s0
/etc/selinux/([^/]*/)?modules/(active|tmp|previous)(/.*)?   system_u:object_r:semanage_store_t:s0

Another curiosity thing again - I wonder what would have happened had you run a restorecon -Fv /etc/selinux/config before you installed the missing package. Crazy!