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