How to remove a package: Re-install the host
Most sysadmins treat installing boxes as the last resort. And they have a good reason: It can take more than a day to do a semi-complex install.
It should take 5 minutes of clock time and 10 seconds of sys-admin time. And if you can make it take 5 minutes/10 seconds, you'll give your sysadmins a LOT more flexibility in managing large numbers of hosts.
You want to re-provision hosts from task A to task B? Re-install them. You're not quite sure why one host is acting a little flakey? Re-install it. The patch set for a box has gotten insanely long, and it will take longer to patch than to reinstall? Re-install it. You want to update your hosts from RHEL5 to RHEL6? Test it once, then write a script to do them over night. Yes, I'm serious.
Approaches
This is the new hotness. And it does have some advantages of manageability. And it does allow you to quickly create new (virtual) machines.
But it makes all your computers slower. (Raising CPU utilization through virtualization. Same work, same computers, more costs, more CPU utilization! What could possibly go wrong?!)
If you have a need put a box up for a week then take it down for 3 months, like in a QA lab, then perhaps virtualization is better. But for production you can get all the benefits with either of the two solutions below. So use them instead.
The basic idea here is that the "base image" that gets installed on every box turns into a glorified GRUB, or you just always PXE-boot. Your host contacts an image server, downloads the real image, which installs the software automatically and brings up a fresh box. Every boot.
Upside: No bit-rot on the host. You can change between images very easily (just reboot). No power spent spinning hard drives. And to be honest, the local network is faster than a local disk anyway.
Downsides:
changing the image can still be a pain, depending on your tooling. If you've got tooling that makes changing the image easy, then you really could just use that tooling on normal boxes, and skip that whole net-boot thing.
You didn't need that 1G of ram for that ram disk, did you?
You didn't need that network that's pushing out the boot images, did you?
My opinion: It's a good solution if you don't have a real image server. Or if you really don't need local hard drives. But in most cases you do, and building a real boot server isn't that hard. So do that instead.
The standard PXE boot solution. Your PXE boot server is hooked into your CMDB. You reboot the box into PXE-boot mode, and the server gives it an image that does a net-install. Or you give the target box an initrd.img that goes and does a net-install. Same thing.
Then your net-install box is hooked into your CMDB to figure out how to configure/install the box.
And you're done. This is where you want to be.
Cobbler: http://cobbler.et.redhat.com/