Like many I’ve experienced the problem of failing to install Windows Live Messenger or the Windows Live Essentials bundle (Messenger, Mail, Photo Gallery, etc.), where the installer (“wlsetup-custom.exe”) goes almost all the way through, but eventually it encounters a problem, and installation is rolling back.

Then you get the window telling you: “Try installing Windows Live programs again. Programs were not installed because the installation was canceled. aborted:0×80004004”. Yet trying to reinstall fails over and over again (uninstall or restart won’t help either).

After many frustrating hours, here is how I solved it.

First of all I noticed that the installer was always rolling back at the same stage of installation. In my case it was while trying to install Windows Live Toolbar (you can see when it goes wrong by looking at the installer’s status message on the bottom of the installer). Later I found that indeed the toolbar was causing the problem: I had an old Windows Live Toolbar in Japanese which could not be uninstalled, and while trying to install the new Windows Live (which was in English) it caused the failure. Anyway, here’s how to solve the problem:

(*) Warning: the following walkthrough is unorthodox; use it only if you already tried installing Windows Live the standard way (meaning: uninstalling it first, restarting the PC, etc). Also: the following steps require some PC knowledge, as well as a fair amount of patients.

Installation Steps
1) Uninstall all existing Windows Live products. If some products can’t be uninstalled, we will remove them later manually.
2) In Internet Explorer, open the Internet Options window. 

3) Under Programs tab, select “Manage add-ons”.

4) Disable all Widows Live add-ons.

5) Close Internet Explorer.
6) Go to the directory in which Live products were installed (typically: Program Files directory), and delete all the “Windows Live” folders which exist there (e.g.: “C:\Program Files\Windows Live”, “C:\Program Files\Windows Live Toolbar”, etc).  If some of them can’t be removed, restart the PC and try deleting them once more. If delete fails again, restart in “safe mode” and delete the directories, and then restart normally (not in safe mode).
7) Open the Registry Editor (press: WIN+R and then type: “regedit” and Enter). 
8) Search and delete all “Windows Live” entries, or at least all the entries of the product that gave you trouble (“Windows Live Toolbar” in my case). This is a tedious task – there are zillions of them. Moreover, some may not be deletable (but you can excuse them). 

9) Now restart the PC and install Windows Live  – this time it should work!

Good Luck !!