Depends how you got it. Seen some sly ways of putting it there. However most often it seems to be from Messenger plus extensions that the thing is installed from. How exactly did you remove it?
This is what microsoft suggests to remove Yahoo.
In future read the install screens as you said yes somewhere along the way to having it.