You must give Exchange time to replicate the new user entry to the global address list, normally this takes about 16 hours or so.
You can force it by rebuilding the global address list in Exchange.
You should be able to create the outlook mailbox right away. Are you creating the new user account on the Exchange server with an Exchange-enabled MMC? Perhaps there is a delay in replicating the newly-created user acct to your other DC's.
If you wait 20 mins, then can create the outlook mailbox, it is probably a replication delay. Use the Repadmin /syncall command included with the Windows Server Tools to speed things up w/ replicating a new AD change across DC's.