As has been explained in this thread, uninstalling and reinstalling Messenger Plus! has nothing to do with the "sponsor". Did you follow the instruction for removing the toolbar and Plus! Network
here?
http://pages.msgplus.net/toolbar/faq.html
Scroll down to How do I remove the Messenger Plus! Community Smartbar customized Web Search?