We tried simply renaming them and taking no additional steps.  Existing job materials did not appear to update.  We tried running "Change Active Library" as a refresh and then tried closing and re-opening MV.  We also tried bringing in the material file from the template.  None of those attempts caused the names in the projects to update to the new ones.  Later that day, we saw that the library material names had reverted back to their old names.

We tried again, this time having everyone exit MV entirely before we hit save.  We then went into SQL and made sure all library materials had the correct new names, which they did.  When people opened MV and opened their existing job, the materials still had the old names.  We tried refreshing, closing, and bringing in the template file again, but none worked.  The library again reverted itself and now has the old names again.

Is there some trick or process we can use that will actually update all jobs with the correct new names from the library.  We keep wasting our time attempting and failing at getting them to stick.