If you update the name format in CRM system settings, new records created will have the new full name format, but what about existing records?

The format of the full name will not be updated on existing contacts automatically. To change the format on existing contact records, update something about the name on the existing records. For example, you can use a workflow or an SSIS job to update the first or last name fields with the existing data. After this, the full name will be updated on the existing records.