You mentioned deleting in both directions, so this might help. For the mail to be deleted succesfully from your device, the mail needs to be in the Deleted Items folder within the mailbox. So, if you do a SHIFT-Delete, the mail will stay on the device. Also, if a delegate deletes the mail from Outlook, it will also stay on the BlackBerry.
Cheers
Paul