Instale autoruns e procure por todas as ocorrências do "yahoo", para ver se alguma parte de yahoo messenger ainda está instalado e começa com o computador. Se sim, vá e apague o arquivo (e talvez seu diretório), então reinicie. Para ter mais certeza, eu apenas o renomeia, em vez de excluir, e aguardo alguns dias para ter certeza de que nenhum dano foi causado.
Na próxima vez que desinstalar um aplicativo, use o Revo Uninstaller Freeware para garantir que o aplicativo foi completamente desinstalado , sem quaisquer sobras.