Hi @lalajee ,
If you are using Azure AD Connect to sync the accounts, it could be that the UPN is not changing in Azure.
You could follow below document to connect Azure with powershell first.
Connect to Microsoft 365 with PowerShell - Microsoft 365 Enterprise | Microsoft Learn
Run below command to updating the UPN after connect to Azure.
Set-AzureADUser -ObjectId oldname@contoso.com -UserPrincipalName NewName@contoso.com
If the issue still persist. You could also try to download the address book in outlook manually.
If the response is helpful, please click "Accept Answer" and upvote it.
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.