Does Exchange Online have an internal search Index for people ?

Hello everyone,

I'm managing users with Office 365 E3 licences. We have an hybrid Exchange Online / Exchange On-Premise architecture.

My problem is the following: After I create an user with E3 licence, and after AAD Synchronisation between Azure / AD, the user is created on Azure but also the email mailbox (Exchange Online).

But within the "To" input, through the Autocomplete suggestions, this user cannot be found, neither with Outlook Desktop Client nor with OWA Outlook (Web version of Otlook), even several hours later of the creation.

I can use the mailbox (can login to OWA Outlook), can send / receive. So the mailbox is created correctly. I can connect to Exchange-Online via PowerShell and get all informations for the target mailbox (like others) with:

 Get-Recipient -Identity "email address removed for privacy reasons" 

And also via 

Get-Recipient -Anr "elon"

(this gives me "Elon, Musk" as a suggestion through PowerShell).

But why the autocomplete cannot suggest me this user ? Through the GAL (Global Address List) the user is visible (when I click on "To" button within Outlook Desktop Client -> Popup showing the Global Address List). But it's not suggested automatically, like others (old users).

I made several hours of searches but I do not found any concluant result.

My only question is: does Exchange Online infrastructure have an internal Search Index for People ? And if so, how often it's updated to include newly added users to the tenant?

On what is based the autosuggestions within the inputs "To" / "CC" / "CCI". In my case (at least), the search for autosuggestions cannot be based on Global Address List / Offline Address Book from our On-Premise Exchange server, because EVEN the Web based OWA Outlook cannot find the newly created user!

Thank you in advance for your precious help!

Best Regards,

Adam J.