Te propongo una solución muy sencilla para que acabes con este problema...
Tienes que irte a Mail y abrir un nuevo correo.
En el momento en que estés escribiendo el destinatario, selecciona autocompletar con el nombre del contacto que quieres eliminar.
Una vez que aparezca en la barra de direcciones, señala el icono en el recuadro azul que aparece en la parte derecha y haz clic en "Eliminar dirección"
De este modo quedará eliminado y no aparecerá cuando estés escribiendo direcciones.