On uninstallin the sponsor make sure u totally close down your internetbrowser (from systray also) that way the searchbar can be uninstalled aswell (u can't uninstall something thats in use).
I would suggest:
1. reinstall with sponsor..again yes
2. uninstall - this time with internetbrowser shut as i said above
3. reboot (this way all traces will be deleted)
4. reinstall without sponsor
/ 
