Contacts visible in mailing list group, not on hold or otherwise dnd, but skipped by mail out
As I've added to my question, it turns out the problem wasn't with the emails or the DND settings - the missing contacts all had a NULL value for is_deceased, and apparently CiviCRM interprets this as them being dead (rather than just missing information). When you edit the entire contact record, this is flagged, but because I was just checking the emails and DND settings in place, I hadn't noticed this.

Setting all the null values to 0 fixed the problem - I ran the following SQL query on the civicrm_contact table:

UPDATE civicrm_contact SET is_deceased = 0 WHERE is_deceased IS NULL;

(As per the answer here: https://civicrm.stackexchange.com/a/7396/610 )

Following that, all the relevant contact records reappeared in the mailing list recipient count.

(Double checking the import field mapping, it turns out I didn't tell it to skip that field - CiviCRM exports the field as empty if is_deceased = 0, so I guess importing it did overwrite the existing values)