Parece probable que esto no sea un error. Depende de cómo hayas eliminado al usuario desde la consola.
Desde la consola, intenta buscar:
UserEmail.where(email: '<tu_correo_electrónico_eliminado>')
Si eso te da un resultado, intenta buscar al usuario con el user_id que se devolvió:
User.find_by(id: <id_del_registro_de_correo>)
Mi suposición es que no se devolverá ningún usuario, porque el correo electrónico pertenecía al usuario que eliminaste. Si ese es el caso, debería ser seguro llamar a destroy! en el registro del correo electrónico. Antes de intentar esto, asegúrate de tener una copia de seguridad actualizada de tu sitio.
Si el correo electrónico sí pertenece a un usuario existente, no elimines el registro del correo electrónico.