CiviMail: Mystery Unsubscribes
I had this question also and just figured it out!

Civimail always includes a List-Unsubscribe header in the messages it sends out (https://issues.civicrm.org/jira/browse/CRM-3251).

That header is invisible to most recipients and is intended as a way for mail clients to provide easy and standardized unsubscribe mechanisms (http://www.list-unsubscribe.com/). 

I note that google doesn't seem to do anything with it, though they do expose the list unsubscribe option for mailman lists, or used to .. But, it appears that Windows Live does use it, so anyone using that software that receives Civimail can use it.

The only clue I had was in my apache logs - the time of the unsubscribe matched a soap request that came in via UAS/CiviSMTP that handles the bounces for this domain.

Thanks to Leyla UAS/CiviSMTP support (http://www.civismtp.com/) for confirming this idea.

For bonus points, assuming you really only want people to opt-out instead of unsubscribing, you can include this in a custom extension or module, changing 'hook' to the name of your custom extension or module.

function hook_civicrm_alterMailParams(&amp;$params, $context) {
  if ('civimail' == $context || 'flexmailer' == $context) {
    $params['List-Unsubscribe'] = str_replace('mailto:u.','mailto:o.',$params['List-Unsubscribe']);
  }
}