メッセージを削除するとゴミ箱に移動されますが、ゴミ箱フォルダがない場合にはゴミ箱を使わずに削除されます。
ゴミ箱を使わないようにするには、ゴミ箱のフォルダのプロパティの一般ページで[ゴミ箱]のチェックを外すか、ゴミ箱フォルダ自体を[フォルダ]-[削除]を選択して削除してください。