>>同じアドレスは作れないの一点張り・・・

確かに、技術的には同じ解約や変更された旧アドレスを再度利用することは可能です。
しかしながら、サーバー側のプログラムの仕様上、それをしようとすると技術者2人がまる1日仕事しても足りないような作業が必要になる。
（サーバー機のバックアップ、再インスコ等だけでもかなり時間かかるよ。一般人のPCリカバリなんかとはわけが違う）
しかもそれは、その時間帯に同サーバーを使うユーザーがメールを利用できないことを意味する。

1人の顧客のためだけに、なんでも言うこと聞いてられない。
できる限り多くのお客様を優先させなければならない。
これが本当の、カスタマーサティスファクションなんだから。