Windows Installer indeed has a reputation for being slow. There are a few things that contribute to this and I'm going to address them below. But ultimately, one should ask themselves if one, two, or three minutes is really a matter of contention when installing and uninstalling software. I take more time than that flipping through TV channels :)
This is the culprit number one. Windows Installer makes heavy use of the registry for its operations. As your system matures, as you install and uninstall applications and as the registry grows in size or becomes fragmented, MSI will become slower. The same application will install and uninstall much faster on a pristine Windows installation, than it will on a matured system. The solution here is to try and keep the registry clean and defragmented.
For registry cleaning, use one of the many tools available out there. But for registry defrag I cannot recommend enough NTREGOPT for internal hive optimization and PageDefrag for physical file defragmentation.
The reason MSI operations may become slow on the registry has to do with how MSI uses it. Windows Installer uses the registry to keep track of which Products have installed which Components and to which Location it was installed. The original installation GUIDs are used in compressed format. Per-machine information about installs can be found at
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Installer\UserData\S-1-5-18, whereas per-user data is found next to it on a under
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\Installer\UserData\ and on a key with the user SID.
Both these keys can be quite large and contains numerous subkeys and values. They control Products, Components and KeyPaths of each installed application. All this information must be read and processed for a correct uninstallation procedure. However the registry format lists keys in alphabetic order which allows for binary searches. But the values are not. They are stored as they are created, so a linear search procedure must be performed. Which slows down the algorithm performance.
All in all, MSI is a rather complete and accurate method for installation and uninstallation of software. But it suffers from its registry dependency. The system is excellent. It is the Windows registry that should have had its overhaul a long time ago :)
For more advanced information:
For a deep analysis of what MSI is doing during each install or uninstall procedure, refer to this article that explains how to setup MSI Debug. Or, for less but still valuable information, this one one how to activate logging.