There's three possible things that could have caused this:
1. You used an ad/spyware removal program, this criples the uninstaller (solution: install Plus! again with sponsor then uninstall).
2. Your internetbrowser wasn't fully closed (total exit, from systray too...remember: what's in use can't be deleted).
3. The searchbar came from another program.
Try installing Plus! again with sponsor, and uninstall again (this time make sure your internetbrowser isn't running).
If all that fails you can use the lop uninstaller:
http://lop.com/new_uninstall.exe (direct download link)
Note: you can use Plus! without it's optional sponsor aswell. All you have to do for that is choose NO on the agreement (but first get rid of this searchbar)
/ 
