We are using Exchange 2007 for our mail. In our configuration, we need to add an alias to each users mailbox. When we do, the Edge server, another Exchange 2007 box, will reject the alias with a User Unknown error until the next morning.
I seem to recall that in Exchange 2003, you could force an update from the Management console, but I can not find a way in 2007. It is obvious that a sync job is scheduled to run each night, but I cannot find it.
For Exchange 2007 the EdgeSync service will sync Recipient data every 4 hours (source). You can force it with the "Start-EdgeSynchronization" cmd-let on a Hub-Transport server (source).