同じ Perl オブジェクトの DESTROY メソッドが何度も呼ばれていたら...
本当に同じオブジェクトか?
本当にそれが同じオブジェクトなのかどうかは確かめておきましょう。本来一つしか存在しないはずのオブジェクトでも、何らかの手違いで複数個生成されていたりするかもしれません。
fork していないか?
オブジェクトを作った後に fork していると親と子の両方でそれぞれ DESTROY が呼ばれることになります。ファイルやプロセスなど外部とのやりとりがあると、 DESTROY だけでなく fork すること自体が悪影響を及ぼしているかもしれないので要注意です。親子プロセスのタイミングに依存して確率的にエラーが発生するなど、何が起こっているのか把握すること自体が難しいかもしれません。
fork してからオブジェクトを作るようにするのが理想的な解決策ですが、そうもいかないこともあるでしょう。親プロセスでだけそのオブジェクトにアクセスするなら、オブジェクトの初期化時の \$\$ を覚えておいて、 DESTROY 時の \$\$ と比較すると親プロセスかどうか判別できます。
あまり無いとは思いますが、複数スレッドを使っている場合も同じことが起こり得ます。その場合はプロセスIDだけでなく、スレッドIDのようなもののチェックも必要です。
新しく参照を作っていないか
DESTROY 内で新たに他の変数からそのオブジェクトへの参照を作ると、 DESTROY 後にオブジェクトが破棄されず、次にその参照が消えた時に再び DESTROY が呼ばれることになります。
例: https://gist.github.com/wakaba/6773867
この例では最終的にスクリプト全体の終了時に DESTROY が呼び出されて
DESTROY created new reference to dead object 'Package1' during global destruction.
... エラーが発生するので気づくことができます。実際には DESTROY の処理がもっと複雑で、こうわかりやすいエラーにはならないかもしれません。