Should simply work as above indicated.
Could maybe caused by a Windows rights/privileges issue.
Do you have admin rights? Is UAC disabled?
Was Mozilla Firefox (and/or MS Internet Explorer) still active when you tried uninstalling the toolbar?
Maybe try in safe mode.
Maybe also read this thread:
Can't remove BS.Player Search from firefox