People that usually say they've just "done it" usually haven't done it properly, so please try again.
Make sure you follow the instructions carefully, with
every step I mentioned.
Are you sure you deleted the temporary files, cache, contacts folder and registry keys? Then restart your computer, checked Windows Update
(update Windows Installer) and reinstalled Messenger?
99% it will fix your problem, because it removes everything related to WLM and installs them fresh, thus getting rid of most problems.
And with the first link... did you exit Messenger, delete contacts folder, check date & time, firewall, server certificate, then restart?
...
What error are you getting now?
You may want to consider repairing or reinstalling Windows .. or checking for
errors.