First you need to open up the Exchange System Manager and navigate to Recipients > Offline Address Lists
Second, double click on the Default Offline Address List
Third, under update interval click the Customize button.
From there, select a time that is closest to your current time and wait for it to pass. Outlook should update automatically. And your employees won't have to manually type in the new users full email address.