I had an issue creating a user in our domain, things are on track now, except one thing: I had to manually add the email@example.com entry with the Exchangemgmgt console. Most users don't have the recent entry in their copy of the GlobalAddressList in outlook, so mails send internally are failing. Other user, who see the new entry have no issues whatsoever.
I tried forcing an update via powershell "get-globaladdresslist | update-globaladdresslist" and manually re-requesting the addressbook in outlook, but this didn't do the trick.
What can I do so everyone gets the info?