iOS Mail App And Exchange 365 - email address lookup from global address list

Good afternoon; have noticed something that's affecting multiple iPhones in our organization. As noted we're a Exchange 365 shop and are using iOS devices with the latest OS; our clients all use the Mail app for their company Exchange mail.

The issue is this: sometimes when a user types in a name of a company employee, and that employee is not in their contacts, or in their 'recent addresses' cache, the iPhone will locate and display the entry from the global address list in a few moments. Other times, with other names, it never returns a hit from the global address list. So some names work, some don't.

To make it more confusing, if you type in a name it doesn't return a hit on, and after a moment, hit the backspace key twice (to shorten the last name) it then instantly finds the entry in the GAL.

My suspicion is that shorter names are found very quickly and partial last names also return hits faster than a full name; I noticed that if the full last name is short, it also seems to return an answer faster.

Curious to hear if others experience this and if it's consistent for you, and also for any insight.