Ich hatte mal ein ähnliches Problem.
Ich konnte irgendwann nicht ins Internet obwohl mein Router connected war. Und diese Toolbars erschienen bei mir auch die ganze Zeit und bei meinen Favoriten waren irgendwelche Links vorhanden, von denen ich gar nicht wusste.
Hab einfach mein Anti-Virus-Programm den Computer durchsuchen lassen und mit Anti-Spyware-Programme diverse Dateien löschen lassen, auch Dialer.
Danach ging das Internet wieder und die Dateien waren auch weg.
Wie das mit MSN abläuft kann ich nicht genau sagen, aber es ist durchaus möglich, das diese Dateien dafür sorgen, dass es nicht funktioniert.