..one might be add/remove programs in your control panel - is it not listed there?
Download MS Anti Spy Ware Beta (how ironic, using MS Anti Spyware to remove its own spyware!). In there you can go Tools, Advanced Tools, System Explorers. You can then go to IE BHOs (browser helper objects). I use google toolbar so it is listed there, your MSN one should be and you can remove it from there.