Olá Adriana,
O que pode ter acontecido, foi teres eliminado o contacto, sem o bloquear, e teres nas definições de privacidade a possibilidade de pessoas que não estão na tua lista de contacto, entrarem em contacto contigo.
Para impedires pessoas que não estão na tua lista de contactos de entrarem em contacto contigo, activa a opção "Só pessoas incluídas na minha lista de autorizados podem ver o meu estado e enviar-me mensagens" que se encontra em "Ferramentas" -> "Opções" -> "Privacidade".
Espero ter ajudado.
Cumprimentos