Yikes!
First off, look for anything blatently wrong in the Add/Remove Programs list. If you see something that's affiliated with Yahoo!, yank it out. (sounds like you already did this though).
Then run "MSCONFIG" and look under the Startup Tab. Scroll down this list and look for anything with Yahoo! (or anything wierd). Take the checkmarks off, close the program and reboot to see if the problem goes away. If things get worse, run the program again and put the checkmarks back in.
Oh, and don't forget to write a nasty letter to Yahoo!, and probably to a computer magazine or two. PC World has a watchdog which will go after Yahoo if this crap is happening to your system without your knowledge. MaximumPC has something similar too. Spread the word and get these spuds put out of business once and for all.