Your CiviCRM installation may have undead contacts. Contacts are marked as deceased in CiviCRM by setting the is_deceased column to 1; living contacts are marked with 0. However, it's possible for import mistakes to cause contacts to have a value of null for is_deceased. The result is that the contacts don't appear as dead when you view them, but they're excluded from mailings and other features that filter on is_deceased = 0. The same goes for Do not mail, Do not email, and so forth.
A recent question on StackExchange, along with the Halloween holiday, prompted me to write an extension that checks your system for zombies. It uses the new Status Messages page to display a notice with the fields with an inappropriate null value:
Because it's using these new features, it's only available for CiviCRM 4.7, but you should download and test a copy of your site with the new version anyway.