Following our telecon discussion I dug deeper into the mail/smtp RFCs and was reminded that there's a difference between the mail's envelope and header/body. That is, the BCC recipients are stripped from the header along the way (removed from the end-user's view) but not from the envelope because, obviously, otherwise the receiving mail server wouldn't be able to deliver the mail to it's (BCCed) recipient.
That said, this means we really don't want to use large BCC lists (although SMTP requires servers to allow for at least 100 RCPT entries per mail) because the receiving mail server will most likely treat it as being spam and act accordingly (see your analysis above). So the only alternative is to send individual mails to avoid that, which is the recommended approach anyway and the very reason why commercial mass mailing services exist. Now, as we also don't want to use Drupal's batch system and have to user wait until all mails got sent individually, I looked into potential alternatives. Some mail MTAs (SMTP servers) support splitting/grouping mails with multiple recipients. In case of exim we could try to set the max_rcpt option to 1 to enforce a single recipient per mail. While that puts a higher load on the SMTP server it shouldn't really matter in our (edge) case. If things are too slow we might be able to speed things up using remote_max_parallel but I wouldn't use that right away as some remote/receiving servers might reject that or treat it negatively in some way.
Bonus tip, just in case you didn't know: exigrep makes it much easier to track mails in the exim log files