Sending private messages between users
By default, giving a role the permission to delete messages will not delete the message for the other user. I just tested this and it works as you require.

As for only allowing messages between certain users, you can prepopulate the "To" field with /messages/new/[nid]. So on the user page or in views or whatever, you can create this link using tokens or replacements. 
Then disable the field with a custom module. Savvy users could change the [nid] in the url or even the html in the page so this depends on how secure it needs to be. They'd need to know another user's nid to be able to do this but they can only know that if they can already view the user.

function CUSTOMMODULENAME_form_alter(&amp;$form, &amp;$form_state, $form_id) {
  if ($form_id == 'privatemsg_new') {
    $form['recipient']['#disabled'] = '1';
 }
}