Emails are deleting in the mailbox once again!
I feel like a retard.
I missed the very obvious: It was a setting on the device that allows for synchronisation to occur from the device to the mailbox for deleted items.
Happens that we recently replaced both of the handhelds that I experienced this problem on and since this had coincided with the BES Manager upgrade we did, I was looking for the problem on the wrong end!