Description of problem:
Let have package A and package A-selinux, which define selinux policy for A.
Package A-selinux have in %post section 
 semodule -i A.module
 restorecon /file/of/package/A
When you run 
 rpm -Uvh A A-selinux
then files from A package has wrong context (sometimes).
If you run
 rpm -Uvh A
 rpm -Uvh A-selinux
then it is OK. Reverse order is OK to. You just could not run it together.

Version-Release number of selected component (if applicable):
# rpm -qa |grep selinux
libselinux-devel-1.33.4-5.1.el5
libselinux-python-1.33.4-5.1.el5
selinux-policy-2.4.6-203.el5
selinux-policy-devel-2.4.6-203.el5
spacewalk-monitoring-selinux-0.6.10-1.git.29cb6e0f582984620bf455cf4d67627380c20eca
libselinux-1.33.4-5.1.el5
libselinux-utils-1.33.4-5.1.el5
selinux-policy-targeted-2.4.6-203.el5

How reproducible:
sometimes (see steps to reproduce and additional info)

Steps to Reproduce:
Download attached rpm files. It is very minimalized versions of packages from RHN satellite, where we find this behavior. I believe it can be stripped more, but this should be enough for you guys to test without installing all 150 packages we have in our product.

Let first install it without selinux package. That file got var_lib_t:

# rpm -Uvh perl-NOCpulse-Scheduler-1.58.12-1.git.e8b11458fb42a0ffacd01104d6a7d30888771997.noarch.rpm
Preparing...                ########################################### [100%]
   1:perl-NOCpulse-Scheduler########################################### [100%]
[root@dri//tmp]# ls -ldZ /var/lib/nocpulse/NPkernel.out
drwxr-xr-x  root root system_u:object_r:var_lib_t      /var/lib/nocpulse/NPkernel.out

Now install selinux package. That file will get spacewalk_monitoring_var_lib_t:

[root@dri//tmp]# rpm -Uvh spacewalk-monitoring-selinux-0.6.10-1.git.29cb6e0f582984620bf455cf4d67627380c20eca.noarch.rpm
Preparing...                ########################################### [100%]
   1:spacewalk-monitoring-se########################################### [100%]
....
[root@dri//tmp]# ls -ldZ /var/lib/nocpulse/NPkernel.out
drwxr-xr-x  root root system_u:object_r:spacewalk_monitoring_var_lib_t /var/lib/nocpulse/NPkernel.out

Now remove it and install both packages in one transaction and that file got var_lib_t:
[root@dri//tmp]# rpm -e spacewalk-monitoring-selinux perl-NOCpulse-Scheduler
/sbin/restorecon reset /var/lib/nocpulse context system_u:object_r:unlabeled_t:s0->system_u:object_r:var_lib_t:s0
...
[root@dri//tmp]# rpm -Uvh perl-NOCpulse-Scheduler-1.58.12-1.git.e8b11458fb42a0ffacd01104d6a7d30888771997.noarch.rpm spacewalk-monitoring-selinux-0.6.10-1.git.29cb6e0f582984620bf455cf4d67627380c20eca.noarch.rpm
Preparing...                ########################################### [100%]
   1:spacewalk-monitoring-se########################################### [ 50%]
/sbin/restorecon:  error while labeling files under /etc/notification
/sbin/restorecon reset /var/lib/nocpulse context system_u:object_r:var_lib_t:s0->system_u:object_r:spacewalk_monitoring_var_lib_t:s0
/sbin/restorecon reset /var/lib/nocpulse/NOCpulse.ini context system_u:object_r:var_lib_t:s0->system_u:object_r:spacewalk_monitoring_var_lib_t:s0
/sbin/restorecon reset /var/lib/nocpulse/.ssh context system_u:object_r:var_lib_t:s0->system_u:object_r:spacewalk_monitoring_var_lib_t:s0
/sbin/restorecon reset /var/lib/nocpulse/.ssh/nocpulse-identity.pub context system_u:object_r:var_lib_t:s0->system_u:object_r:spacewalk_monitoring_var_lib_t:s0
/sbin/restorecon reset /var/lib/nocpulse/.ssh/authorized_keys context system_u:object_r:var_lib_t:s0->system_u:object_r:spacewalk_monitoring_var_lib_t:s0
/sbin/restorecon reset /var/lib/nocpulse/.ssh/nocpulse-identity context system_u:object_r:var_lib_t:s0->system_u:object_r:spacewalk_monitoring_var_lib_t:s0
/sbin/restorecon:  error while labeling files under /var/lib/notification
   2:perl-NOCpulse-Scheduler########################################### [100%]
[root@dri//tmp]# ls -ldZ /var/lib/nocpulse/NPkernel.out
drwxr-xr-x  root root system_u:object_r:var_lib_t      /var/lib/nocpulse/NPkernel.out

Actual results:
/var/lib/nocpulse/NPkernel.out get var_lib_t. But since selinux module has been loaded in %post prior installation of  perl-NOCpulse-Scheduler, I would expect that any file installed after spacewalk-monitoring-selinux will get selinux context as defined in this politics.

Expected results:
/var/lib/nocpulse should have spacewalk_monitoring_var_lib_t

Additional info:
[root@dri//tmp]# getenforce
Permissive
Note: It seems that it depends on order of package installation. This bug only appear if spacewalk-monitoring-selinux is picked up before perl-NOCpulse-Scheduler. Since the rpm picked up order randomly, you may find that it will install perl-NOCpulse-Scheduler as first. Try to swap name of packages on command line, try to run it more time, try to wait and run it later ... till you get the order the same as I have in steps to reproduce.

Jnovy sugggested to use %posttrans instead of %post which seems to make workaround, so it is not critical for us, but I still suppose this is serious bug, which do something which is not expected.