What's your on-premise Exchange server version? Please verify if the issue only occurs on outlook for mobile, whether outlook client or OWA can search users in directory properly?
Where are the user and the users you want to search locate?
I tried in my environment, when I type some letters for the user then search directory, the user in directory will show below.
In addition, we could also Get in-app help for Outlook for iOS and Android for further support.
Tap your profile photo and then the ? > Contact Support.
If an Answer 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.