"Do not email" privacy setting and CiviMail
Your analysis is correct, the list of recipients is build when the email is scheduled, not when it's sent

In practice, it shouldn't differ too much, but they are some edge case, like possibly your "Do not email" contacts that might have changed between the time you scheduled the email and it was sent

Depending on what logging configuration you have, you might have more info and find out the timeline: check on the "log" tab to see when the contacts have been modified and by whom (they are some changes that aren't properly logged, but you might find the information you need to understand these cases)