Limpiar el sistema para mi es formateo a bajo nivell, instalación de windows y sus respectivos programas de seguridad que utilices. Después de esto cambia la contraseña de tu cuenta robada.
Para mayor seguridad no accedas a tu email en redes públicas o redes en a las que se conecta mucha gente anque no sea una red pública. Si tienes mucha necesidad de acceder en estos lugares a tu email create un email nuevo por si el ordenador en que estas estuviera infectado y anulara la seguridad de https.
Si tienes portatil accede por https y no tendria que pasar nada en principio.
Cambiate de mail y create una cuenta en Gmail, yahoo tiene seguro menos seguridad (y menos dinero

Saludos y suerte.