If you have removed from IE search provider, please check if there are no suspicious Toolbars and extensions (screenshot). Also, please make sure to uninstall any unwanted/unused search assistants from Add or remove programs (e.g. Babylon search, MySearch, etc.).
Should the issue persist, please provide us with an msinfo output from your system for brief analysis.