Para que no queden indicios de dicho contacto lo que tienes que hacer es reconstruir tu lista de contactos... ya que todos los contactos que has tenido una vez, siempre dejan rastros.. para reconstruir la lista yo en lo personal uso una herramienta que te ofrece el sitio
http://www.msngeeks.comes la opcion
Contact List Rebuilder , el sitio te pide la contraseña de tu msn.. esto es mas que obvio que genera dudas al querer utilizarlo por una cuestion de seguridad... pero yo en lo personal lo uso hace ya 1 año y medio y nunca tuves problemas... doy fe que el sitio es seguro...
Ah .. una cosa mas.. ademas de dicho contacto molesto.. se limpian todos los contactos que has tenido y ya no estan.. asi que ten cuidado con no tener un historial de aquellas personas que si planeas volver a agregar en un futuro cercano ya que de ellos tampoco quedaran rastros..
SAludoS!