Quick reminder to self (and others): the Linksys WAG200G ADSL Annex-A (or B) modem/router and Windows Vista do not play well together for Windows Live Messenger. You will need to start netsh.exe from an elevated command prompt and run the following commands:
set global autotuninglevel=disabled
After that you can login to the Messenger service again. Works with firmware 1.01.05.