Do you know if your environment is hybrid?
If so, you could confirm with IT admin if he creates users in the on-premises Active Directory first, and then synchronized to Azure AD. Otherwise, the online users cannot be discoverable by on-premises users. For more information, please refer to this article.
If my suggestion has no help, I want to confirm some other questions with you:
Could you search these users normally before?
Does anyone else have the same problem?
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.