Save Outlook 2016 email address auto complete entries & then import them into new Outlook 2016 profile

A company I am working for is currently using Outlook 2016 to send and receive emails through their Gmail email service. All users currently have thousands of email auto complete entries within their Outlook profiles.

These auto complete entries are important since when the users type the first few characters of someone's email address or name the correct email address will appear as an auto complete entry within Outlook (see the screenshot).

Next week I will be switching them over to using Office 365 and will be creating new Outlook profiles for each and every user that will be communicating with the Office 365 server instead of with the Gmail servers.

We don't want for the users to have to regenerate their email address auto complete entries once again.

What can be done to preserver or to regenerate the Outlook user's email auto complete entries so that when the users type the first few characters of an email address or name the email address will be suggested within the email auto complete entry?

I will be willing to purchase a commercial utility to either migrate these email auto complete entries or to regenerate them based upon previously sent and received emails from the current to the new Outlook 2016 email profiles if necessary.