Check internet options -> security -> trusted sites and see what you've got listed. If a site is listed, it can reinstall the toolbar every time you visit one of their web pages. I'd take everything off the list, and see what messages pop up about "wanting to add this site to your list of trusted sites".

Matthew