Have you tried uninstalling the MSN Toolbar from the Control Panel/Add-Remove Programs section?

Tried using System Restore to a time BEFORE the MSN Toolbar was installed?

Tried "repairing" Internet Explorer by reinstalling Service Pack 2 for XP?

Hope this helps.

Grif