Correct Display Name but Incorrect Username when searching for users who have had a name change.

[George_W_Argiropoulos]

I want to start off by saying I am aware of how to clear Teams cache and the extended sync period for changes.  That being said any user that has had a name chage in our org has this issue.  As an example
Patrick.Stewart gets a name change and is now  Patrick.Warburton.  After Teams is showing the updated display name and clicking on their profile is showing all the correct info when searching and typing in Patrick Warburton,  Patrick Warburton will be listed as the Display Name, but underneath it will show (Patrick.Stewart).  Clearer example below.  I can't figure out where this is coming from and like I mentioned previously this is after everything else has Synced. Cache has been cleared and it displays this way for anyone who looks them up in the search.  Can anyone offer any insite into this?

Patrick Warburton
(Patrick.Stewart)

[#2]

Was both the display name and username actually changed? It's easy to not change both

[#3]

@Ed Woodrick 

Yes, both have been changed and are reflected correctly everywhere except in Teams search.  I've added a screen shot.

[#4 · Accepted solution]

This issue is resolved. I had to open up the accounts and come through every single attribute looking for anything at all that referenced the old name. There were a couple of things that the top level admins said were legacy and were no longer used in our environment, but I removed them anyway. Due to how long it takes Teams to sync changes I did not follow best practice and turn them off one by one. Thanks for anyone who viewed this thread.