Sometimes when you send a message that you are certain has never been sent before, you will still see on the delivery that some of the constituents were filtered out under the category "Has been sent this message already".
Did you start deliveries, cancel them, and restart them in a fairly short period of time? If so, that is likely what caused this. When you first configure a delivery and hit send, the system immediately marks the constituents who are in the delivery as having received the delivery. However, when you cancel the delivery, it takes some time for those marks to be cleared out. So if you configure a resend very quickly after a cancel, the constituents who are a part of the resend that are still marked as a part of the now canceled delivery don't get included in the resend. Once some time has passed (usually about an hour), if you re-resend those emails to the exact same audience, they will usually send just fine as the system should be done processing the cancel.
For other reasons why constituents may have been filtered out of a delivery can be found here.