I saw this problem for the first time, where Windows Live Messenger would crash on startup. I don't know how it was installed since this was someone else's PC, but when I tried using it with a freshly created user account, Live Messenger worked as intended.

This told me there was a setting problem with the user account that Live was installed on.

I only had to rename the following registry keys:

HKEY_LOCAL_MACHINE\Software\Microsoft\MSNMessenger
HKEY_LOCAL_MACHINE\Software\Microsoft\Windows Live Contacts
HKEY_LOCAL_MACHINE\Software\Microsoft\Windows Live

I ended up renaming Windows Mail as well, but this wasn't recreated.

When I launched Live Messenger after doing these things, Messenger launched without crashing and recreated these keys. I didn't have to turn off UAC or DEP to make this fix work.

Next I'll explain to this fellow why they shouldn't use Internet apps with an admin account, even with UAC turned on, but that's another battle for another day. :-/