Link goes to post that helped the most (I don't make this stuff up myself)!
I found that my Server 2003 x64 Enterprise Terminal Server was taking a stupid long time to install and remove applications. It was making me crazy! This server has 1TB of hdd space (500+GB free), hardware RAID (with a battery, so write-back wasn't an issue), dual Quad-Core Xeon's, and 8GB of RAM. Everything I installed took an eternity (7-Zip took 45 minutes!)
After much reading I found a forum post saying that someone had used Process Explorer while removing software and was seeing huge amounts of data being copied out of the registry that contained Hewlett-Packard in its key. Further searches have found that when users connect to a Terminal Server and fallback drivers are configured it will try to install the users print drivers in the server, fail, go for the fallback driver, then never remove the installed (nonworking) driver info from the registry.
All the extra info in the registry was being read and written to a backup of the registry during software installs, taking a really long time. Deleting these keys and their subkeys fixed the trouble.
REMEMBER TO BACK YOUR REGISTRY UP BEFORE MAKING CHANGES TO IT!