OK, seguindo os conselhos, encontrei aqui , removi todos os aplicativos do Windows Live do meu computador e tentei instalar novamente.
No entanto, o uso do instalador da Web não funcionou e me deu o mesmo erro. Eu então baixei o wlsetup-all.exe, e a instalação funcionou.
Este endereço é fornecido no link acima para o instalador completo do Live Messenger: link
Eu escolhi fazer o download do mesmo endereço que o instalador da web que baixei em download.live.com, então não posso garantir esse endereço.
Não sei se a remoção dos aplicativos existentes ajudou em tudo, mas o Messenger lembrou-se de todas as minhas configurações, por isso estou feliz.