Membership not extended to all related contacts
The solutions below took place inside the CiviCRM GUI:

For most, I had to disable and re-enable all relationships and subsequently edit and save the membership.

In a few cases, even this didn't work. For those records, I also edited the membership and specified a number of allowed related records before saving (I also subsequently went back in and cleared out that number with no ill effects).