Hi Moralgriever
Messenger Plus! is not malware. Where are you updating from? (Which site).
Please read the instructions here for uninstalling the toolbar:
http://pages.msgplus.net/toolbar/faq.html
You may also refer to the thread here:
http://shoutbox.menthix.net/showthread.php?tid=98787
Let me know if that works for you.