Hey Cris,
We recently made a change so that all available data is used if the quick search fails. The quick search fails if there are over 1,000 results. We tested this locally and noticed no performance issues on domains with over 10,000 users. How many users do you have on your domain? The main driver behind this change was that not all addresses were populating when trying to autocomplete. I recommend opening a ticket with support and providing them with this information. If they can replicate the issue with a config-only copy of your domain, we may be able to make some optimizations.
Kind regards,
Zach Sylvester
Software Developer
SmarterTools Inc.
www.smartertools.com