I have no idea why this does work sometimes and sometimes not, I will look for that.
Isn't possible that you actually don't sync filesystem before the reboot? I.e. your installer does install the 'rpm' tool but you just reboot and it's never written to disk. This might explain its randomness.