これはおそらくバグではないようです。コンソールからユーザーを削除した方法によります。
コンソールから以下のように検索してみてください。
UserEmail.where(email: '<your_deleted_users_email>')
結果が返ってきた場合は、返された user_id でユーザーを検索してみてください。
User.find_by(id: <email_record_id>)
推測ですが、削除したユーザーにそのメールアドレスが割り当てられていたため、ユーザーは返されないでしょう。その場合、メールレコードに対して destroy! を呼び出すのは安全です。実行する前に、必ずサイトの最新のバックアップを取得してください。
もしそのメールが既存のユーザーに割り当てられている場合は、メールレコードを削除しないでください。