The NPSP once deleted empty Household Account records, but that's no longer the default behavior. Now, it renames them to "Anonymous Household". From What Happens When I Delete a Contact:
When you delete a Contact ...
In the past, if the Contact was the last one in the Household Account, the Account was also deleted. This is no longer the case. The Household Account is not deleted, but is renamed to Anonymous Household.
You will most likely find your missing Households under that name.