I have several Windows Server 2003 Terminal Servers exhibiting similar behavior. Specifically, when installing or uninstalling programs which use MSI, it takes an extremely long time for the process to complete.
For example, on an unaffected machine a particular software package installs in under 2 minutes. On a problem machine, this same install can take 1-2 hours during which time the msiexec.exe process hangs at 50% CPU (on a dual core machine). Usually it's hanging at the stage where it's preparing to install (or similar wording).
After this extremely long wait, the installation eventually "breaks loose" and proceeds to completion.
I've run the MSI cleanup utility from the MS Support website. I've run registry "cleanup" tools. Nothing seems to help.
Another example-- uninstalling Microsoft Silverlight, which on most PCs only takes a few seconds, took nearly 10 minutes on this server with the msiexec process hanging at 50% CPU. Eventually the initial stages passed and the process completed successfully.
Just bringing up Add/Remove Programs listing in Control Panel can take 1-2 minutes with the rundll32.exe process hanging at 50% CPU (on a dual core machine).
Not sure where to look or what to do next.