It seems the issue here is a mixup between a contact's associated company, and a contact's 'Company Name' property. These are two distinct things:
'Company Name' is a default contact property that exist on contact records and is most often used as a form field.
An associated company is a distinct company record that is associated with a contact record. This is most often the result of automatic email domain association.
A contact's 'Company Name' property will not automatically update to reflect the name of the contact's associated company; this is intentional, and is intended to prevent the automated contact <-> company association from overwriting data provided by the contact.
It's not possible to pull the associated company's 'Name' property when requesting contacts using the 'Get all contacts' endpoint, since that value isn't stored on the contact record. You'll instead need to request the associatedCompanyId property and pull information on the company records you're interested in.