Weak references are deleted BEFORE the DESTROY method of the object they point to runs?

No.

$ perl -MScalar::Util=weaken -MDevel::Peek -wE'
   my $y;
   sub DESTROY {
      Dump($y,0);
      Dump($_[0],1);
   }
   {
      my $x = bless({});
      $y = $x;
      weaken($y);
   }
'
SV = IV(0x99a738c) at 0x99a7390        <-- $y
  REFCNT = 2
  FLAGS = (PADMY,ROK,WEAKREF)          <--   Still a reference (ROK)
  RV = 0x998c768                       <--   Still referencing %$x
SV = IV(0x998c8a4) at 0x998c8a8        <-- $x
  REFCNT = 1
  FLAGS = (ROK,READONLY)
  RV = 0x998c768
  SV = PVHV(0x99917a8) at 0x998c768    <-- %$x
    REFCNT = 1
    FLAGS = (OBJECT,OOK,SHAREKEYS)
    STASH = 0x998c658   "main"
    ARRAY = 0x99a6210
    KEYS = 0
    FILL = 0
    MAX = 7
    RITER = -1
    EITER = 0x0
    BACKREFS = 0x99a7390               <-- %$x is weakly ref-ed by $y
    SV = IV(0x99a738c) at 0x99a7390
      REFCNT = 2
      FLAGS = (PADMY,ROK,WEAKREF)
      RV = 0x998c768
[download]

Sorry, no time to look into your code today.

Update: I was misusing weaken. Fixed.