Parece provável que isso não seja um bug. Depende de como você excluiu o usuário pelo console.
Pelo console, tente pesquisar por:
UserEmail.where(email: '<seu_e-mail_de_usuário_excluído>')
Se isso retornar um resultado, tente pesquisar o usuário com o user_id que foi retornado:
User.find_by(id: <id_do_registro_de_e-mail>)
Minha suposição é que nenhum usuário será retornado, pois o e-mail pertencia ao usuário que você excluiu. Se for esse o caso, deve ser seguro chamar destroy! no registro de e-mail. Antes de tentar isso, certifique-se de ter um backup atualizado do seu site.
Se o e-mail pertencer a um usuário existente, não exclua o registro de e-mail.