The Exchange installation is deployed with Edge server in PA.
All incoming messages to a customer mailboxes on a particular domain are not delivered, they are being rejected by Edge server.
If a customer's domain with mailboxes is not propagated to the Edge server yet, it can not receive mail to any address on that domain.
The configuration/recipients data is stored in ADAM (Active Directory Application Mode) on Edge server.
The synchronization of configuration data to Edge server occurs at one-hour intervals. The synchronization of recipient data occurs at four-hour intervals.
If you want to synchronize Active Directory changes to ADAM immediately, use the Start-EdgeSynchronization cmdlet in the Exchange Management Shell.
You can run the following command manually on Exchange server:
C:\WINDOWS\system32\WindowsPowerShell\v1.0\PowerShell.exe -PSConsoleFile "C:\Program Files\Microsoft\Exchange Server\bin\exshell.psc1" -command ". Start-EdgeSynchronization"
Read the following Microsoft KB article for details about the Start-EdgeSynchronization cmdlet - http://technet.microsoft.com/en-us/library/bb123512.aspx