Shoutbox

Perhaps Windows Installer 3.1? (Windows 3.1 is 16-bit (with optional 32-bit extensions) operating system from like 15 years ago which had a flaky-at-the-best-of-times networking stack, and most certainly doesn't support WLM)

I do not know why the problem would only re-occur every few days.

I do know that if you delete certain shortcuts and run the program using another MSI-generated shortcut then Windows Installer will repair the installation and regen the shortcut you deleted.

If the WU [Windows Update] logo appears then disappears, this indicates it launched, quit without cleaning up (ie removing the icon; ie crashed), and then was respawned.

3 things to look for:
1) Mal/Spy/Ad-ware causing dodgy DLL conflicts or preventing programs from running via code injection or the like. Download HijackThis! and either peruse the log yourself or upload it to their forums.

2) Corrupt system files preventing WU from actually launching. You can check this (hopefully) by first opening Event Viewer, then restarting the Automatic Updates from services.msc, and then selecting the System log in EV. If there's any warnings or errors, inspect and report back.

3) If you can't be bothered, manually making a shortcut to c:\program files\windows live\messenger\msnmsgr.exe should prevent Windows Installer from being invoked - but does not fix the root of the problem.