Você excluo o contato? Quer dizer que você apagou os dados tipo número e nome? O mais fácil se for um contato conhecido, é tentar falar com ele por meio de algum chat que vocês dois estejam usando.
Se for contato profissional, igualmente, ele pode ser contato por meio de redes sociais ou diretamente na empresa onde ele trabalha.
Você pode verificar nos arquivos da memória interna do telefone ou então na nuvem associada, se você tem conta no celular para fazer os backups dos dados.