削除フラグ(del_flag)を1にしただけですと、EC-CUBE上では見えなくとも、根本のMySQLデータベースにはレコードとして残ってしまっています。
(del_flag=1、というフィールド値を持ったレコード行が存在するということですから、当然といえば当然ですよね？)

ですので、完全に重複しないようにしたいのであれば、サーバー側のMySQLデータベースから直接削除する必要があるのではないかと思います＾＾；

もしくは、未確認ですが、削除フラグを1にした行のカテゴリ名を、今後絶対使わないであろう名前に変更して再度アップしたら、少なくとも名前が重複することはないのではなかろうかと・・・？