Sending private messages between users EDITED
The excellent Privatemsg module provides a wealth of functionality but some sites might not need/want this degree of complexity. Rather than starting with something complex and disabling/removing features, I would like to think about ways to build something relatively simple from basics.
Using the basic infrastructure of D7 what are the ways one could create a simple messaging system that allows user A to message user B, and both of these corresponding users to delete this message individually (i.e. user A deletes message 1, but user B does not; therefore user B can still see message 1)?
How might message threads (i.e. successive related messages) be managed and displayed?
How well would the solution scale (e.g. 1,000,000 messages, 100,000 threads, etc.).
Thank you.
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';
 }
}