Você pode usar o Recuva (gratuito), para recuperar dados apagados ou perdidos no disco rígido se for no computador, Já no celular, você deve usar um gerenciador para Android, para poder acessar a memória interna e tentar recuperar dados que ficam, sempre, gravados nela, mesmo sendo apagados. Mas, esse programa não tinha como ativar o histórico das conversas?