Why do Windows Installers (.msi files) take so much longer to uninstall than other installers?

Windows installer first systematically creates a system restore point, which is a quite slow operation.

Also from the article entitled, appropriately, "Windows Installer sucks", an excerpt:

It used to be that installation would consist of a program executing and taking a few simple steps to install your software, then do the reverse on uninstallation.

That's not how Windows Installer works. Instead of running a program to simply install and let it be done with, it examines the state of your system, then examines the state of the database that is the program's installer, then does a series of overcomplicated calculations about how to reconcile the two.

It seems that, instead of running an installation script, it goes about solving a traveling salesman problem. Which is why it runs so slow. Or at least, that's my impression.

I also add that Windows installer keeps all information in the registry, which is not the world's fastest database.

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 :)

The Registry
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.

Windows installer has many big advantages for corporate deployment, some of which I have described here: https://serverfault.com/a/274609/20599

Much of the slowness of a Windows Installer session is due to its rollback capabilities. Firstly it creates a restore point prior to install or uninstall (provided system restore hasn't been disabled). Then it will back up all affected files during both uninstall and install to ensure that the system can be restored to its original state should an error occur.

Another contributing factor is that all components in the MSI will be registered in the registry. This involves some overhead.

For compiled MSI files some time is also needed to extract the install files.

See this answer for technical details for speeding up MSI installations.