Pon los contactos en gmail y olvidate de todos esos problemas, te pasa por no tenerlos en gmail y tenerlos en el movil, y ademas agravado por la sincronizacion de facebook, para borrar un contacto enlazado, primero quita el enlace y luego borra el contacto.