Search for a style in Find/Change and the old style name appears in parenthesis next to it.

I’ve never seen anything like that, either. If IDML doesn’t work, what version exactly are you using? The current version is 21.5.1.73.

​@leo.r shout out and double down on the IDML route to see if it fixes. 

If it doesn’t. 

Try rebooting the computer first. See if it’s any better.

Then:

1. In Find/Change, clear both Find Format and Change Format with the little trash-can buttons, then select the renamed style again.
2. If you’re using a saved Find/Change query, delete/recreate that query.
3. Close and reopen the document and check again.
4. Check whether it happens in a brand-new document after creating and renaming a style. That will tell us immediately whether this is document-specific or application-wide.
5. Only if it occurs in all documents would I start looking at resetting InDesign preferences.
6. Failing that - Creative Cloud Cleaner Tool.

Can you show a screenshot of exactly where you’re seeing New Name (Old Name). The text in parentheses could potentially be identifying something other than a cached style name, and seeing the actual Find Format dialog would probably settle it quickly.

All I know is I can’t reproduce it (in a much simpler document than yours, for sure). Maybe there are some complex inter-style relationships and/or specific cases of style application that affect this? Try to export your doc as IDML, then resave IDML - will it make a difference?