Civi does not email to some contacts (Not CiviMail, just mail)
Thanks to michaelmcandrew's comment I investigated deeper and found the reason being a bug. Created issue https://issues.civicrm.org/jira/browse/CRM-19876 which is really weird but contains a somehow simple patch (https://github.com/civicrm/civicrm-core/pull/9676).