Hi, @Nesma
Based on your description, I understand that you can't search for a user in the global address list, and only in the sub-address list.
Here are some suggestions you can try.
1.In Outlook 2010 and later, go to the "Send/Receive" tab, tap "Send/Receive Group", and then tap "Download Address Book". In the Select Address Book drop-down menu, select Global Address List and click OK.
2.There may be some policies applied to the Global Address List (GAL) that limit the visibility of the user.
If none of the above is a problem, then it may indeed be related to the update. In order to save manpower and improve resource efficiency, Microsoft encourages users to do granular search instead of unlimited browsing, and this change affects browsing in any list of online addresses for more than 500 users.
In addition, I noticed you raised the same issue here as well, you can stay tuned to this thread as well. Searching users in global Address lists in Exchange/Teams Online - Microsoft Community
If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".