It seems likely that this is not a bug. It depends how you deleted the user from the console.
From the console, try searching for:
UserEmail.where(email: '<your_deleted_users_email>')
If that gives you a result, try searching for the user with the user_id that was returned:
User.find_by(id: <email_record_id>)
My guess is that no user will be returned because the email belonged to the user you deleted. If that is the case, it should be safe to call destroy! on the email record. Before trying this, be sure that you have an up-to-date backup of your site.
If the email does belong to an existing user, do not delete the email record.